一文看懂二分查找(文末附练习题)

八月 13, 2020

二分查找

每次写二分我都得找几个小时的bug，写此篇记录一下到底该怎么写二分

遇到查找就两种，哈希或二分，本文介绍二分查找。
简单的二分查找很好写，但是细节部分很多。
对于一个数组[1,2,3,4,5,6,7,8,9]查找7 。思路是这样的：
有high和low两个指针，分别指向末尾和头部，每次取中间位置的元素，如果这个值大了，就让high=mid-1.如果值小了就让low=mid+1，循环下去，就能找到值，当low>high时候跳出循环。时间复杂度是logn，空间复杂度是常数。
一定要注意二分只能对有序数组操作

//基础的二分代码，本文均采用升序数组
public int binSearch(int[] arr, int start, int end, int target) {
        //左闭右闭区间[0,arr.length - 1]
        int low = start, high = end;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target){
                low  = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

上面的区间是[start,end]，有些写法是[start,end)，差异会很大，比如循环条件是low<high,high=mid，本文都采用第一种方式
这种二分只能应对最简单的情况，但是做题遇到的会比这种花哨的多。

第一种：第一个大于等于查找值的元素

对于数组{2,5,6,6,8,12,15}，查找9返回12，查找15返回15，查询6返回index=2的6

public int binarySearchR(int[] arr, int start, int end , int target) {
      //第一个大于等于给定值的元素
      int left = start, right = end, mid = 0;
      while (left <= right) {
          mid = (left + right) / 2;
          if (arr[mid] < target) {
              left = mid + 1;
          } else if (arr[mid] >= target){
          //如果当前元素前一个比给定值小，说明这个是第一个大于等于给定值的元素，
          //如果这个已经是最开始的元素，直接返回
              if (mid == 0 || arr[mid - 1] < target) return mid;
              else right = mid - 1;
          }
      } 
      return - 1;
  }

第二种：最后一个小于等于查找值的元素

对于数组{2,5,6,6,8,12,15}，查找9返回8，查找15返回15，查询6返回index=3的6

public int binarySearchL(int[] arr, int start, int end , int target) {
      //最后一个小于等于给定值
      int left = start, right = end, mid = 0;
      while (left <= right) {
          mid = (left + right) / 2;
          if (arr[mid] > target) {
              right = mid - 1;
          } else {
          //基本原理和上一个差不多，都是比较当前位置和下一个的关系
              if (mid == end || arr[mid + 1] > target) return mid;
              else left = mid + 1;
          }
      } 
      return -1;
  }

binarySearch源码

java的Arrays包封装了一个binarySearch方法。下面是他的源码。

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
//传进来是[0,arr.length]，所以下面high会减1
        int low = fromIndex;
        int high = toIndex - 1;

        while(low <= high) {
            int mid = low + high >>> 1;
            int midVal = a[mid];
            if (midVal < key) {
                low = mid + 1;
            } else {
                if (midVal <= key) {
                    return mid;
                }

                high = mid - 1;
            }
        }
		//System.out.println("low = "+low+" high = "+high);
        return -(low + 1);
    }

最后返回太妙了，负数代表没有这个数，low+1表示这个数应该存在的位置，其他的都和最开始的代码一样。不过这种写法无法应对有重复数字的查询。

总结

二分查找要形成自己的写法，不要今天是low<high，明天是low<=high，这样很容易就会搞混，细节部分要保持始终如一。
源码是最好的算法。
先总结这么多，其他的情况之后再补充。

最后附上几个二分查找题：
209长度最小的子数组
 1300转变数组后最接近目标值的数组和
 1482制作m束花的最小天数

查看评论