变体二分查找

查找第一个值等于给定值的元素

public int bsearch(int[] a,int value) {
    int low = 0;
    int hight = a.length - 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 == 0) || (a[mid - 1] != value)) {
                return mid;
            } else {
                high = mid -1;
            }
        }
    }
    return -1;
}

a[mid]跟目标value的大小关系有三种情况：大于、小于、等于。

• 对于a[mid] > value的情况，需要更新high=mid-1；
• 对于a[mid] < value的情况。需要更新low=mid+1；
• 当a[mid] = value时：如果查找的是任意一个值等于给定值的元素，a[mid]就是要找的元素。如果查找的是第一个值等于给定值的元素，需要进一步确认：代码中如果mid=0，那么这个元素已经是数组的第一个元素，那它肯定是要找的元素；如果mid!=0，但a[mid]的前一个元素a[mid-1]!=value，那么a[mid]就是要找的元素；如果经过检查后发现a[mid-1]=value，则a[mid]肯定不是要找的第一个值等于给定值的元素，需要更新high=mid-1，要找的元素肯定出现在[low,mid-1]之间。

查找最后一个值等于给定值的元素

public int bsearch(int[] a,int value) {
    int low = 0;
    int high = a.length - 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 == a.length -1) || (a[mid + 1] != value)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}  

• 当a[mid] = value时：如果mid=0，a[mid]已经是数组中最后一个元素，那它肯定是要找的元素；如果a[mid]的后一个元素a[mid+1]!=value，那么a[mid]是要找的元素；如果经过检查后发现a[mid+1]=value，那a[mid]不是最后一个值等于给定值的元素，需要更新low=mid+1，要找的元素肯定出现在[mid+1,high]之间。

查找第一个大于等于给定值的元素

public int bsearch(int a[],int value) {
    int low = 0;
    int high = a.length -1;
    while(low <= high) {
        int mid = low + ((high -low) >> 1);
        if(a[mid] >= value) {
            if((mid == 0) || (a[mid - 1] < value)) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

• 如果a[mid] < value，那要找的值肯定在[mid+1,high]之间，所以更新low=mid+1；
• 对于a[mid] >= value的情况，首先判断a[mid]是不是要找的第一个值大于等于给定值的元素。如果mid=0,a[mid]前面已经没有元素就是第一个元素，那么a[mid]就是要找的元素；或者a[mid]前面的一个元素a[mid-1]小于指定值value，那么a[mid]就是要找的元素。如果a[mid-1]>=value，那么说明要找的元素在[low,mid-1]之间。

查找最后一个小于等于给定值的元素

public int bsearch(int[] a,int value) {
    int low = 0;
    int high = a.length -1;
    while(low <= high) {
        int mid = low + ((high -low) >> 1);
        if(a[mid] > value) {
            high = mid -1;
        } else {
            if((mid == a.length -1) || (a[mid +1] > value)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

扩展

凡是用二分查找能解决的，绝大部分更倾向于用散列表或者二叉查找树。二分查找更适合用在“近似”查找问题，用其他数据结构比较难实现。
变体二分查找实现注意细节问题：

• 终止条件
• 区间上下界更新方法
• 返回值选择