Binary Search
問題
針對有序的數(shù)組跨嘉，實現(xiàn)二分查找算法吃嘿。
例子：已知數(shù)組array： [2, 7, 8, 12, 34, 44, 56] ，和目標值 target, 求目標值在數(shù)組中的下標亮瓷，如果不存在返回-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]
//由于數(shù)組中不相等的情況更多搓侄，如果每次剛開始時就要判斷相等，將浪費不必要的時間讶踪。
if (value < target) {
left = mid + 1
} else if (value > target) {
right = mid - 1
} else {
return mid
}
}
return -1
}
更多
獲取更多內容請關注微信公眾號豆志昂揚:
- 直接添加公眾號豆志昂揚；
- 微信掃描下圖二維碼柱查；
