二分查找也称折半查找
算法要求
- 必须采用有序存储数据结构
- 必须按照关键字大小有序排列
思想
将n个元素分成大小相等的两部分，取a[n/2]与x做比较，若x = a[n/2]，则找到该元素，算法结束，如果x < a[n/2]，则证明x在左半边，故在数组的左半边查找，如果x > a[n/2]，则证明x在右半边，故在数组的右半边查找，以此类推
时间复杂度
时间复杂度为O(logn)
代码如下（JavaScript）
function binarySearch(arr, x) {
var low = 0;
var high = arr.length - 1;
while (low <= high) {
var middle = parseInt((high + low) / 2);
if (x == arr[middle]) {
return middle;
}
else if (x < arr[middle]) {
high = middle - 1;
}
else {
low = middle + 1;
}
}
return -1;
}
var arr = [1, 2, 3, 4, 5];
binarySearch(arr, 3); //2
