本文共 1799 字，大约阅读时间需要 5 分钟。

#二分查找及其扩展#

• 二分查找法
  • 时间复杂度
    • O(logn)
  • 实现
    • 递归

public int binarySearchV2(int[] a,int low,int high,int value) {        if(low>high) return -1;        while (low<=high){            int mid = (low+high)/2;            if(a[mid]  == value){                return mid;            }else if(a[mid] > value){               return binarySearchV2(a,low,high-1,value);            }else {               return binarySearchV2(a,mid+1,high,value);            }        }			return -1;    }

- **非递归**

public int binarySearchV1(int[] a,int n,int value){       int low = 0;       int high = n-1;       while(low<=high){           int mid = (low+high)/2;           if(a[mid] == value){               return mid;           }else if(a[mid]>value){               high = mid - 1;           }else{               low = mid+1;           }       }       return -1;    }

• 注意点
  • 退出循环的条件是low <= high
  • （low+high）容易溢出 改为 low+(high-low)/2 ==> >>1
  • low 和 high的更新
• 扩展
  • 顺序访问及查找
  • 基于数组
  • 数据量太大不适合，数据量太小也不适合
• 相关变形题目
  • 查找第一个值等于给定值的元素
  • 查找最后一个值等于给定值的元素
  • 查找第一个大于等于给定值的元素
  • 查找最后一个小于等于给定值的元素
• 分析
  • 以上几个都是二分查找的变形题目，需要学会举一反三，相信大部分人一看代码马上就能懂了

/**     * 获取第一个等于给定值的值     * */    public static int getFisrtEquals(int[] a,int n,int value){        int low = 0;        int high = n-1;        while(low <= high){            int mid = low + ((high-low)>>1);            if(a[mid] >value){                high = mid-1;            }else if(a[mid] 
   
    >1);            if(a[mid] >value){                high = mid -1;            }else if(a[mid]
    
     >1);            if(a[mid]
     
      >1);            if(a[mid]>value){                high = mid-1;            }else{				// 应该就比较好理解了                if(mid==n || a[mid+1]>value) return mid;                else low=mid+1;            }        }        return -1;    }
     
    
   

• 想要写出一个 bug free的二分查找也不容易，需要考虑 循环的终止条件，区间的上下界值的选择以及返回值的选择

转载地址：http://chiii.baihongyu.com/