基本概念

查找是作为编程一个比较基础的一个功能点,其中比较流行的就是二分查找,其核心思想就是在不断的缩小查找的范围,而且是以lgn的数量级,所以比较受欢迎

实现

对于二分查找我们需要做的一个核心点就是获取中间位置,一个的做法都是直接进行除法计算:

  1. (low + high)/2

但是这里有一个比较麻烦的问题,假设这个high的值很大,超过了int类型的最大值,这个计算公示就会造成溢出问题。那么怎么解决这样一个问题呢。
我们利用数学公示进行一个拆分:

  1. (low + high)/2 = low / 2 + high/2 = (high - low)/2 + low

其实这个还会造成溢出问题,那么最终极的解决办法是怎么处理呢,当然是带符号移位:

  1. (high + low) >>> 1;

实现模版

具体的实现可以参考如下的代码:

  1. public class BinarySearch{
  2. public int search(int[] array, int target){
  3. int low = 0;
  4. int high = array.length;
  5. //这里需要区分到底要不要进去的问题
  6. while(low < high){
  7. int mid = (low + high) >>> 1;
  8. if(array[mid] < target){
  9. low = mid+ 1;
  10. }else if(array[mid] > array[high]){
  11. high = mid -1;
  12. }else{
  13. return mid;
  14. }
  15. }
  16. }
  17. }