二分查找及其扩展

#二分查找及其扩展#

• 二分查找法
  • 时间复杂度
    • 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] <value){
                low = mid+1;
            }else {
                // 如果mid已经到数组第一位肯定是第一个等于value 或者mid=value且前一位不等于value
                if(mid ==0 || a[mid-1] != value) return mid;
                // 否则高位等于mid-1,相当于往前移一位
                else high = mid-1;

            }
        }
        return -1;
    }

    /**
     * 获取最后一个等于给定值的
     */
    public static int getLastEquals(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]<value){
                low = mid+1;
            }else{
                if(mid == n-1 || a[mid+1]!=value) return mid;
                else low = mid+1;
            }
        }
        return -1;
    }

    /**
     * 获取第一个大于等于给定值的
     */
    public static int getFirstMoreThanEquals(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){
                low = mid+1;
            }else{
                if(mid==0 || a[mid-1]<value){
                    return mid;
                }else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
    /**
     * 最后一个小于等于给定值的
     */
    public static int getLastSmallerEquals(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(mid==n || a[mid+1]>value) return mid;
                else low=mid+1;


            }
        }
        return -1;
    }

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