LeetCode 解题思路 32（Hot 100）

解题思路：

1. 初始化指针​​： 设置左指针 left 为 0，右指针 right 为数组长度减 1。
2. 循环查找​​： 在 left <= right 的条件下循环：

• 计算中间索引 mid，避免整数溢出（mid = left + (right - left) / 2）。
• 若中间元素等于目标值，直接返回 mid。
• 若中间元素小于目标值，说明目标值在右半部分，更新 left = mid + 1。
• 若中间元素大于目标值，说明目标值在左半部分，更新 right = mid - 1。

3. 返回插入位置​​： 循环结束后，left 指针指向的位置即为目标值应插入的位置（保证数组有序）。

Java代码：

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

复杂度分析：

• 时间复杂度： O(logn)。每次循环将搜索范围缩小一半，因此时间复杂度为对数级别。
• 空间复杂度： O(1)。仅使用常数级别的额外空间。

解题思路：

1. 初始化指针： left = 0（指向矩阵左上角），right = m * n - 1（指向矩阵右下角）。
2. 二分查找​​：

• 计算中间索引 mid，并通过 mid / n 和 mid % n 转换为二维坐标 (row, col)。
• 若当前元素等于目标值，返回 true。
• 若当前元素小于目标值，说明目标值在右侧，更新 left = mid + 1。
• 若当前元素大于目标值，说明目标值在左侧，更新 right = mid - 1。

3. 结束条件​​： 若循环结束仍未找到目标值，返回 false。

Java代码：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {        
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; 
            int row = mid / n;
            int col = mid % n;
            
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

复杂度分析：

• 时间复杂度： O(log(mn))。通过一次二分查找完成搜索，时间复杂度取决于总元素数 mn 的对数值。
• 空间复杂度： O(1)。只使用了常量级的额外空间。