二分查找 §

时间复杂度：O(logN)

代码实现 §

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

注意点：

1. 取mid的时候不要使用mid=(low+high)/2，可能会导致越界。如果需要优化性能，可以使用位运算low+(high-low)>>1
2. 不要将low=mid+1和high=mid-1的+1和-1去掉，去掉的话可能会产生死循环
3. 循环退出条件是low<=high，不是low<high