透彻理解二分查找-算法通关村

常见的查找算法有顺序查找、二分查找、插值查找，树表查找、分块查找、哈希查找等等。其实二分查找、插值查找以及斐波那契查找都可以归为一类—插值查找。插值查找是在二分查找的基础上的优化查找算法。
二分查找的价值，请记住：
**凡是在排好序的地方查找的都就可以考虑用二分来优化查找效率。不一定全局都排好才行，只要某个部分是排好的，就可以针对该部分进行二分查找，这是很多题目优化查找的重要途径。**
我们知道二分就是每次只取一半，但是在有些场景下，我们大致知道数据的位置了，就不必折半，取1/3，3/4这样不是也可以吗？当然可以！为了更有通用性，插值查找使用的公式是：
mid = low + (key - a[low]) / (a[high] - a[low]) * (high-low)
分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。分块查找要求把一个数据分为若干块，每一块里面的元素可以是无序的，但是块与块之间的元素需要是有序的。即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推。

1 基本查找

查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，也不需要排序，只需要一个个对比即可，但其实效率很低。

  int search(int[] arr, int key){
          for(int i = 0; i < arr.length; i++){
              if(arr[i] == key){
                  return i;
              }
          }
          return -1;
      }

2 二分查找与分治

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如二分搜索、排序算法（快速排序，归并排序）等等…，任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，⋯。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
二分查找就是将中间结果与目标进行比较，一次去掉一半，因此二分查找可以说是最简单、最典型的分治了。
二分查找，不管是循环还是递归方式，我觉得应该达到写到闭着眼睛，一分钟就能写出来的地步。
这里再补充一个问题，分治和递归是一回事吗？很显然不是。这是两种完全不同的思想，二分查找是分治思想，我们可以使用递归或者循环的方式来做。而很多递归问题也不一定是分治的，因此两个完全不是一回事。

2.1 循环的方式

常见的使用循环的方式来实现二分查找如下：

  public int binarySearch(int[] array, int low, int high, int target){
          while(low <= high){
              int mid = (low + high)/2;
              if(array[mid] == target){
                  return mid;
              }
              if(array[mid] < target){
                  //由于array[mid] 不是目标值，
                  // 因此再次递归搜索时，可以将其排除
                  low = mid + 1;
              }
              if(array[mid] > target){
                  high = mid - 1;
              }
          }
          return -1;
      }

观察上面的代码，有个很重要的细节没有处理，在计算机中，除的效率非常低，一般可以使用移位来代替：
将：int mid = (low + high) / 2;
换成：int mid = (low + high) >> 1;
但是还没完，问题就是假如 low 和 high 很大的话，low + high 可能会溢出：
将：int mid = (low + high) >> 1;
换成：int mid = low + (high - low) >> 1;
只要low和high没有溢出，上面的mid一定不会溢出。
如果你觉得这就没问题了，那你可能会输得很惨，因为当你测试的时候，可能会出现死循环，例如原始序列是1到8，搜索3的时候就死循环了，为什么呢？
这是因为移位的运算符>>优先级比加减要低，所以上面的代码等价结构是这样的：
(low+(high - low))>>1
很明显这不是我们预期的。解决方法也很简单，加括号就行了。所以最终的代码就是：

  public int binarySearch3(int[] array, int low, int high, int target){
          while(low <= high){
              int mid = low + ((high - low) >> 1); // 使用位运算符计算中间索引
              if(array[mid] == target){
                  return mid;
              }
              if(array[mid] < target){
                  //由于array[mid] 不是目标值，可以将其排除
                  low = mid + 1;
              }
              if(array[mid] > target){
                  high = mid - 1;
              }
          }
          return -1;
      }

2.2 递归的方式

递归的话就不必多说了，直接看代码：

  public int binarySearch4(int[] array, int low, int high, int target){
          //递归终止时间
          while(low <= high){
              int mid = low + ((high - low) >> 1); // 使用位运算符计算中间索引
              if(array[mid] == target){
                  return mid;//返回目标值的位置，从1开始
              }else if(array[mid] < target){
                  //由于array[mid] 不是目标值，
                  // 因此再次递归搜索时，可以将其排除
                  return binarySearch(array, mid+1, high, target);
              }else if(array[mid] > target){
                  return binarySearch(array, low, mid-1, target);
              }
          }
          return -1;//没有搜索到
      }

3 元素中有重复的二分查找

假如在上面的基础上，元素存在重复，如果重复则**找左侧第一个**，请问该怎么做呢？
这里的关键是找到目标结果之后不是返回而是继续向左侧移动。第一种，也是最简单的方式，找到相等位置向左使用线性查找，直到找到相应的位置。

  public int binarySearchOfRepeat(int[] array, int target){
          if(array == null || array.length == 0){
              return -1;
          }
          int left = 0;
          int right = array.length-1;
          while(left <= right){
              // 使用位运算符计算中间索引
              int mid = left + ((right - left) >> 1); 
              if(array[mid] < target){
                  left = mid+1;
              }else if(array[mid] > target){
                  right = mid-1;
              }else{
                  //该循环会持续向左移动 mid 指针，
                  // 直到它不再指向目标值或者到达数组的开始位置。
                  // 这样做是为了跳过所有重复的目标值，直到找到第一个出现的目标值。
                  while(mid != 0 && array[mid] == target){
                      mid--;
                  }
                  //说明这是数组中目标值的第一个出现位置，因此返回 mid。
                  if(mid == 0 && array[mid] == target){
                      return mid;
                  }
                  return mid+1;
              }
          }
          return -1;//没有搜索到
      }

注意这里在找到之后的while循环结束后，为什么要返回mid+1，而不是mid呢？这是因为此时 array[mid] 已经不等于target了，例如假如序列为 { 1, 2, 2, 2, 2, 3, 3}，当target=3，当内层的while退出时，array[mid] = 2，因此我们必须返回mid+1。