二分查找算法的前提是有序数组，查找数据和数组中间的元素相比较，相等就返回数组中间下标，如果不等于则取半继续查找。时间复杂度：O(log2 n )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/* 非递归写法 */
function binarySearch(arr, key) {
let low = 0, high = arr.length - 1
while (low <= high) {
let mid = parseInt((low + high) / 2)
if (key === arr[mid]) {
return mid
} else if (key > arr[mid]) {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/* 递归写法 */
function binary_search(target, arr, low, high) {
let start = low || 0
let end = high || arr.length - 1
if(start > end){
return -1
}
let mid = parseInt((start + end) / 2)
if (target === arr[mid]) {
return mid
} else if (target > arr[mid]) {
return binary_search(target, arr, mid + 1, end)
} else {
return binary_search(target, arr, start, mid - 1)
}
}
|
近期评论