vlambda博客
学习文章列表

图解二分查找的递归和非递归实现

    二分查找算法也叫折半查找算法,是一种查找效率非常高的算法。二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

一、复杂度分析
时间复杂度:     
    假设数据集大小是 n,每次查找后数据都会缩小为原来的一半,即除以 2。最坏情况下,直到查找区间被缩小为空,才停止。
    当 n/2k=1 时,k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了 k 次区间缩小操作,时间复杂度就是 O(k)。通过 n/2k=1,我们可以求得 k=log2n,所以时间复杂度就是 O(logn)。
空间复杂度:
    对于非递归实现,辅助空间为常数级别,所以空间复杂度为:O(1)
    对于递归实现,每次方法调用会定义一个mid变量,而上面提到缩小的次数为k,所以方法的调用次数为k+1,所以空间复杂度为:O(log2n+1),即O(logn)。

二、二分查找的递归实现

前提:这里我们只考虑最简单的情况,即有序数组中不存在重复元素,包含重复元素的我们下节再讲
思路分析:
    我们定义一个有序数组的开始下标为begin,结束下标为end,待查找的数据为target,查找过程如下:
  1. 找到数组的中间位置下标mid:int mid = end+((begin-end)/2)
  2. 比较数组中间值和target的大小:
    1. 如果中间值大于target,说明待查找值在mid左边,在左边递归查找;
    2. 如果中间值小于target,说明待查找值在mid右边,在右边递归查找;
    3. 如果中间值等于target,说明找到了待查找值,直接返回
  3. 如果begin>end,结束递归,说明没有待查找的值
图解:

图解二分查找的递归和非递归实现

图解二分查找的递归和非递归实现

代码实现:

public static int binarySearch(int[] arr, int begin, int end, int target) { if (begin > end) { return -1;//返回-1表示没有找到 } int mid = end + ((begin - end) / 2);    if (target < arr[mid]) {//中间值大于查找值,递归向左边查找 return binarySearch(arr, begin, mid - 1, target); } else if (target > arr[mid]) {//中间值小于查找值,递归向右边查找 return binarySearch(arr, mid + 1, end, target); } else { return mid;//返回target在数组中的位置下标 }}

注意:

  • 递归结束的条件:begin>end

  • 中间下标的计算公式:由于int mid = (begin + end) / 2 这个计算公式中(begin + end)存在溢出的风险,所以采用int mid = end + ((begin - end) / 2),或者int mid = (begin + end)>>>1

  • begin和end的更新:low=mid+1,high=mid-1。注意这里的 +1 和 -1,如果直接写成 low=mid 或者 high=mid,就可能会发生死循环。比如,当 high=3,low=3 时,如果 a[3]不等于 value,就会导致一直循环不退出。


三、二分查找的非递归实现
思路分析:
    在非递归实现时,查找过程如下:
  1. 启动一个while循环,只要满足begin<=end,就继续执行

  2. 找到数组的中间位置下标mid:int mid = end+((begin-end)/2)

  3. 比较数组中间值和target的大小:

    1. 如果中间值大于target,说明待查找值在mid左边,将end改为mid-1;

    2. 如果中间值小于target,说明待查找值在mid右边,将begin改为mid+1;

    3. 如果中间值等于target,说明找到了待查找值,直接返回

  4. 如果begin>end,结束循环,说明没有待查找的值

图解:

代码实现:
public static int binarySearch(int[] arr,int begin,int end,int target){ while (begin<=end){ int mid = (begin + end) / 2; if (arr[mid]==target){ return mid;//返回target在数组中的位置下标 } //如果数组中间值比目标值大,说明在左边,那么把end修改为mid-1,然后在左边继续二分查找 if (arr[mid]>target){ end=mid-1; }else{ begin=mid+1; } } return -1;}

注意:

  • 循环的执行条件:begin<=end