Leetcode Hot100 二分查找

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length; // 定义数组长度
        int left = 0, right = n - 1, ans = n; // 分出左边界，目的点，右边界各下标


        // 条件的修改就看是递增还是递减，这里递增
        while (left <= right) {
          // 设定边界条件为 左边 小于等于 右边

            int mid = ((right - left) / 2) + left;// 获取当前情况下的中点索引


          // 更新边界的条件

            if (target <= nums[mid]) {
                ans = mid; // 传入值小于中点值，那么传入的值就插入中点所在
                right = mid - 1; // 右边边界更新为中点减一，继续向左查找
            } else {
                left = mid + 1; // 左边边界更新为中点加一，继续向右查找
            }
        }

        return ans;// 因为设置了ans = mid,所以ans就会偏向单一指定的下标
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target); // 查找目标值所在行
        if (rowIndex < 0) {
            return false; // 如果不满足行的条件，那么说明不存在
        }
        // 通过所在行，查找目标值
        return binarySearchRow(matrix[rowIndex], target);
    }

    // 二分查找第一列，找到目标值所在行
    // 如果目标值不在第一列，返回-1
    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    // 二分查找行，找到目标值
    // 如果目标值不在行，返回false
    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}