二分查找也称为折半查找,主要用在有序集合中进行查找。我们先通过一个猜数字的小游戏来分析。首先我随机写一个0~99的数字,然后你再猜我写的哪一个数字,在猜数字过程中如果你猜大了,我会提示你猜的数字大于我写的数字;如果你猜小了,我会提示你猜的数字小于我写的数字,直到猜中为止。那么如何快速猜中呢?
这里就可以用到二分查找的思想了,假设我写下的数字为16,那么可以通过如下步骤进行猜测:
通过很少的次数(6次)就可以猜到数字。
为了方便用图形表示,我们假设在11~20之间找到16,如下图所示为查找过程,其中 low
和 high
表示待查找区间的下标, mid
表示待查找区间的中间元素下标。
二分查找是针对的一个有序的数据结合,查找思想有点类似分治思想,每次通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。
二分查找的效率是非常高的,时间复杂度为 O(logn)
。
这里讨论的是在有序数组中不存在重复元素的二分查找代码实现,我们实现递归版本与非递归版。
public int binarySearch(int[] nums, int n, int val){ int low = 0; // low表示待查找区间的起始位置的下标 int high = n - 1; // high表示待查找区间的终止位置的下标
while(low <= high){ int mid = low + (high - low) / 2; // mid表示待查找区间的中间位置的下标 if (nums[mid] < val){ // 如上图第2步情况 low = mid+1; }else if(nums[mid] > val){ // 如上图第3步情况 high = mid - 1; }else{ // 当找到该数时,直接返回mid即可 return mid; } }
return -1; // 当数字中没有需要查找的数,返回-1.}
这里需要注意如下几点:
low<=high
而不是 low<high
mid
的取值:不能将 mid
写成 mid=(low+high)/2
。因为如果在 int
类型情况下,当 low
和 high
之和大于 int
类型的最大值,就会溢出,导致结果错误。因此需要写成 mid=low+(high-low)/2
。更进一步,如果要将性能优化到极致,可以使用位运算进行计算, mid=low+((high-low)>>1)
。public int binarySearch(int[] nums, int n, int val){ return help(nums, 0, n-1, val);}
/** * 辅助函数 * @param nums 数组 * @param low 待查找区间的起始位置的下标 * @param high 待查找区间的终止位置的下标 * @param val 待查找的值 * @return 查找到的值的下标,如果没有这个数,则返回-1 */private int help(int[] nums, int low, int high, int val) { // 当数字中没有需要查找的数,返回-1 if(low > high) return -1;
int mid = low + (high - low) / 2; // mid表示待查找区间的中间位置的下标
if (nums[mid] < val){ // 如上图第2步情况 return help(nums, mid+1, high, val); }else if(nums[mid] > val){ // 如上图第3步情况 return help(nums, low, mid-1, val); }else{ // 当找到该数时,直接返回mid即可 return mid; }}
二分查找有着查找效率高的优点,但是并不是所有的情况都可以进行二分查找。