Binary Search
问题
针对有序的数组，实现二分查找算法。
例子：已知数组array： [2, 7, 8, 12, 34, 44, 56] ，和目标值 target, 求目标值在数组中的下标，如果不存在返回-1。
解答
《编程珠玑》的作者Jon Bentley在其书中写到：“90%的程序员写的二分查找程序中都是有bug的， 虽然早在1946 年就有人将二分查找的方法公诸于世，但直到1962 年才有人写出没有bug 的二分查找程序。”
关于二分查找的算法原理再次不做阐述，我们来看写代码时需要注意地方。
func binarySearch(array: [Int], target: Int) -> Int {
var left = 0
var right = array.count - 1
while (left <= right) {
//防止内存溢出, 追求效率也可以使用位运算
let mid = left + (right - left) / 2
let value = array[mid]
//由于数组中不相等的情况更多，如果每次刚开始时就要判断相等，将浪费不必要的时间。
if (value < target) {
left = mid + 1
} else if (value > target) {
right = mid - 1
} else {
return mid
}
}
return -1
}
更多
获取更多内容请关注微信公众号豆志昂扬:
- 直接添加公众号豆志昂扬；
- 微信扫描下图二维码；
