什么是二分法查找
二分查找也称折半查找(BinarySearch),它是一种采用分治策略的算法,他将问题分解为规模更小的的子问题,分而治之,逐一解决。采用二分法查找的前提条件是:要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
二分法查找使用场景
二分法查找适用于数据量较大时,但是数据需要先排好顺序。对于我们很多人来说,还是用于面试……
二分法查找算法设计
设排序元素序列(升序)存储在 arrs 数组,begin、end 指定查找范围,keyword 是指定查找的值。
- 每次从子序列中间 mid 开始比较
mid = (begin + end) / 2
,如果 keyword 与 arrs [mid] 元素相等,则查找成功;否则根据根据 keyword 大小缩小查找范围,若 keyword 较小,则继续在子序列前半段 begin ~ (mid - 1)
查找;反之在后半段 (mid - 1) ~ end
查找。 - 重复 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
|
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]) { begin = mid + 1; } else { 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
|
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]) { begin = mid + 1; } else { end = mid - 1; } return binarySearch(arr, value, begin, end); }
|