算法 - 二分法查找 (Java 实现)

什么是二分法查找

二分查找也称折半查找(BinarySearch),它是一种采用分治策略的算法,他将问题分解为规模更小的的子问题,分而治之,逐一解决。采用二分法查找的前提条件是:要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

二分法查找使用场景

二分法查找适用于数据量较大时,但是数据需要先排好顺序。对于我们很多人来说,还是用于面试……

二分法查找算法设计

设排序元素序列(升序)存储在 arrs 数组,begin、end 指定查找范围,keyword 是指定查找的值。

  1. 每次从子序列中间 mid 开始比较 mid = (begin + end) / 2,如果 keyword 与 arrs [mid] 元素相等,则查找成功;否则根据根据 keyword 大小缩小查找范围,若 keyword 较小,则继续在子序列前半段 begin ~ (mid - 1) 查找;反之在后半段 (mid - 1) ~ end 查找。
  2. 重复 1,直到查找成功,当 begin、end 表示范围失效时,返回 -1 表示查找失败。

时间复杂度

最快:O(1)
最坏:O(logn)
平均时间复杂度:O(logn)

Java 实现

循环实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 二分查找
* @param arr
* @param value
* @return -1 则查找失败
*/
public static int binarySearch(int[] arr, int value) {
int begin = 0;
int end = arr.length - 1;
int mid;
while (begin <= end) { // 边界有效
mid = (begin + end) / 2; // 计算中界
if (arr[mid] == value) { // 如果两个值相等
return mid;
} else if (value > arr[mid]) { // value 较小
begin = mid + 1; //
} else { // value 较大
end = mid - 1;
}
}
return -1;
}

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 递归实现二分法查找
* @param arr [排序完成的线性表]
* @param value [查找的元素]
* @param begin [从第几个元素开始]
* @param end [数组长度 - 1]
* @return -1 则查找失败
*/
public static int binarySearch(int[] arr, int value, int begin, int end) {
int mid = (begin + end) / 2;
// 无效边界
if (begin > end) {
return -1;
}
if (arr[mid] == value) {
return mid;
} else if (value > arr[mid]) { // value 较小
begin = mid + 1;
} else {
end = mid - 1;
}
return binarySearch(arr, value, begin, end);
}