二分查找
小布丁 2018-10-15 算法
二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时,都应该考虑二分查找。如果集合是无序的,我们可以总是在应用二分查找之前先对其进行排序。
# 二分法查找的思路如下:
- (1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。
- (2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。
- (3)如果某一步数组为空,则表示找不到目标元素。
::: 给定一个 n 个元素有序的(升序)整型数组 arr 和一个目标值 key ,写一个函数搜索 arr 中的 key,如果目标值存在返回下标,否则返回 -1。 :::
非递归写法:
function binarySearch(arr, key) {
var left = 0; //数组最小索引值
var right = arr.length - 1; //数组最大索引值
while (left <= right) {
// 取中间值
var mid = Math.floor((left + right) / 2);
if (key == arr[mid]) {
// 中间值与幕目标元素进行对比
return mid;
} else if (key > arr[mid]) {
// 目标元素比中间元素大--> 则表明其目标元素在 分割后的右侧 需要进行数组最小值进一位
left = mid + 1;
} else {
// 反之
right = mid - 1;
}
}
return -1; //left>right的情况,这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
初始条件:left = 0, right = length-1
终止:left > right
向左查找:right = mid-1
向右查找:left = mid+1
递归写法
function binarySearch(arr, low, high, key) {
if (low > high) {
return -1;
}
var mid = Math.floor((low + high) / 2);
if (key == arr[mid]) {
return mid;
} else if (key < arr[mid]) {
high = mid - 1;
return binarySearch(arr, low, high, key);
} else {
low = mid + 1;
return binarySearch(arr, low, high, key);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15