二分查找

二分查找也称 折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

前提条件

数组有序

时间复杂度

二分搜索方法充分利用了元素间的次序关系,采用分治策略,可在最坏情况下用 \(O(logn)\) 时间完成搜索任务

基本思想

将 n 个元素分成个数大致相同的两半,取 a[n/2] 与 x 进行比较。

如果x=a[n/2],则找到 x,算法终止。

如果 x<a[n/2], 则只要在数组 a 的左半部继续搜索 x。

如果 x>a[n/2],则只要在数组 a 的右半部继续搜索 x。

Java 实现

  • 非递归
1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearch(int[] arr, int target) {
if (arr == null || arr.length == 0) return -1;

int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
  • 递归
1
2
3
4
5
6
7
8
9
10
11
public static int binarySearch2(int[] arr, int target, int left, int right) {
if (arr == null || arr.length == 0) return -1;

if (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return binarySearch2(arr, target, mid + 1, right);
else return binarySearch2(arr, target, left, mid - 1);
}
return -1;
}

C 实现

1
2
3
4
5
6
7
8
9
int binary_search(int* a, int left, int right, int target) {
while(left <= right){
int mid = (left + right) / 2;
if(a[mid] == target) return mid;
if(a[mid] < target) left = mid + 1;
else right = mid - 1
}
return -1;
}

References

https://en.wikipedia.org/wiki/Binary_search_algorithm