///Binary Search Recursively. Θ(lgn)
func binarySearch<T: Comparable>(target:T, sortedArray: [T]) -> Int? {
guard sortedArray.count > 0 else { return nil }
return _binarySearch(target: target, sortedArray: sortedArray, low: 0, high: sortedArray.count-1)
}
func _binarySearch<T: Comparable>(target:T, sortedArray: [T], low:Int, high:Int) -> Int? {
guard low != high else { return target==sortedArray[low] ? low : nil }
let mid = (high+low)/2
if sortedArray[mid] > target {
return _binarySearch(target: target, sortedArray: sortedArray, low: low, high: mid)
} else if sortedArray[mid] < target {
return _binarySearch(target: target, sortedArray: sortedArray, low: mid+1, high: high)
}
return mid
}
///Binary Search Circularly. Θ(lgn)
func binarySearch<T: Comparable>(target:T, sortedArray: [T]) -> Int? {
guard sortedArray.count > 0 else { return nil }
var mid = 0, low = 0, high = sortedArray.count-1
while low != high {
mid = (high+low)/2
if sortedArray[mid] == target { return mid }
if sortedArray[mid] > target { high = mid }
else { low = mid+1 }
}
return target==sortedArray[low] ? low : nil
}
let r = try Int.random(above: 0, under: 99)
let s = Array(0...99)
binarySearch(target: r, sortedArray: s)
Binary Search. Θ(lgn)
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 预备知识 【来自维基百科】二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英...
- 【题目描述】 Given two values k1 and k2 (where k1 < k2) and a r...
- 原题 给定两个值 k1 和 k2(k1 < k2)和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围...
- 解題思路 : recursive 作業順序: 往左檢查 left child 只要有符合 > k1 的 node ...
- Search Range in Binary Search Tree 今天是一道有关二叉树的题目,来自LintCo...