教学

https://blog.csdn.net/m0_37302219/article/details/107180126blog.csdn.net

https://leetcode-cn.com/problems/binary-search/solution/li-qing-er-fen-cha-zhao-by-hello1100101/

左闭右闭

JDK里的数组二分查找就是用的这种,循环终止条件是 left>right

//JDK里的代码 private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1;//因为是闭区间，而toIndex是不在区间内的，所以需要-1

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        //这里的low和high分别在mid上进行加一和减一操作，也与左闭右闭保持了一致性
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    //这里针对 low==0 而无法判断是否找到的情况
    return -(low + 1);  // key not found.
}

左开右闭

while (L < R) {
    int mid = L + (R - L) / 2;
    if (nums[mid] == target) {
        return mid
    } else if (nums[mid] < target) {
        L = mid + 1
    } else if (nums[mid] > target) {
        R = mid
    }
}
return L/R; 

左闭右开

while (L < R) {
    int mid = L + (R - L + 1) / 2;
    if (nums[mid] == target) {
        return mid
    } else if (nums[mid] < target) {
        L = mid
    } else if (nums[mid] > target) {
        R = mid - 1
    }
}
return L/R; 

左开右开

while (L + 1 < R) {
    int mid = L + (R - L) / 2;
    if (nums[mid] == target) {
        return mid
    } else if (nums[mid] < target) {
        L = mid
    } else if (nums[mid] > target) {
        R = mid
    }
}
if (nums[L] == target) {
    return L;
}
if (nums[R] == target) {
    return R;
}
return -1; // L

Binary Search in doubles:

- Template:
double lo = initial_lo; // Set initial lower bound
double hi = initial_hi; // Set initial upper bound
double eps = 1e-5;      // Tolerance level

while (hi - lo > eps) {
    double mid = (lo + hi) / 2.0;
    if (condition(mid)) {
        lo = mid; // or adjust hi based on your condition
    } else {
        hi = mid;
    }
}
double answer = (lo + hi) / 2.0;