二分搜索框架

注意事项

-搜索区间需要特别留意：[左开、右开] 还是 [左开、右闭）

• while 终止 是否需要带 =号, 区间与 最开始确定的搜索区间

二分搜索框架

    int binarySearch(int num[], int target) {
        
        // 注意 二分搜索的区间是 [左开，右开]
        int left = 0;
        int right = num.length - 1;
        
        // 所以这里的终止条件是 left > right
        while (left <= right) {
            // (left + right ) / 2 和 left + ((right - left ) / 2) 结果相同
            // left 和 right 太大， (left + right ) / 2 可能溢出
            int mid = left + ((right - left ) / 2);
            if (mid == target) {
                return mid;
            } else if (mid > target) {
                right = mid - 1;
            } else if (mid < target) {
                left = mid + 1;
            }
        }
        
        return -1;
    }

左侧二分搜索边界

    int left_bound(int num[], int target) {
        
        // 注意 二分搜索的区间是 [左开，右开]
        int left = 0;
        int right = num.length - 1;
        
        // 所以这里的终止条件是 left > right
        while (left <= right) {
            // (left + right ) / 2 和 left + ((right - left ) / 2) 结果相同
            // left 和 right 太大， (left + right ) / 2 可能溢出
            int mid = left + ((right - left ) / 2);
            if (mid == target) {
                right = mid - 1;  // 找到后，不返回，收缩右侧边界，继续搜索
               // return mid;  
            } else if (mid > target) {
                right = mid - 1;
            } else if (mid < target) {
                left = mid + 1;
            }
        }
        if (left >= num.length || num[left] != target) {
                return -1;
        } 
        return left;
    }

右侧二分搜索边界

    int right_bound(int num[], int target) {
        
        // 注意 二分搜索的区间是 [左开，右开]
        int left = 0;
        int right = num.length - 1;
        
        // 所以这里的终止条件是 left > right
        while (left <= right) {
            // (left + right ) / 2 和 left + ((right - left ) / 2) 结果相同
            // left 和 right 太大， (left + right ) / 2 可能溢出
            int mid = left + ((right - left ) / 2);
            if (mid == target) {
                left = mid + 1;  // 找到后，不返回，收缩左侧边界，继续搜索
               // return mid;  
            } else if (mid > target) {
                right = mid - 1;
            } else if (mid < target) {
                left = mid + 1;
            }
        }
        if (right < 0 || num[right] != target) {
                return -1;
        } 
        return right;
    }