案例

搜索插入位置（简）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

解题思路

1. 初始化：left指向数组的起始位置，right指向数组的最后一个位置。
2. 循环过程：
   • 如果target小于等于nums[mid]，则target可能在左半部分，所以将right设置为mid - 1。
   • 如果target大于nums[mid]，则target只能在右半部分，所以将left设置为mid + 1。
3. 循环结束条件：当left超过right时，循环结束。
4. 结果分析：
   • 如果target存在于数组中，最终left和right会指向target的两侧，循环结束时left会停在target的位置。
   • 如果target不在数组中，left会停在第一个大于target的元素的位置，这就是target应该插入的位置，以保持数组的有序性。

因此，循环结束时，left指向的位置是目标值应该插入的位置。这是因为算法的设计保证了left始终指向一个“可以插入”的位置，即使这个位置在数组的最末端。

var searchInsert = function (nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = (left + right) >>> 1;
        if (target <= nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

搜索二维矩阵(中)

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

img

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

img

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

解题思路

国家级优化

这个算法的思路是将二维矩阵视为一个一维数组，并在这个一维数组上应用二分查找。这样做的关键在于能够准确地在一维索引和二维索引之间转换。下面是算法的步骤和对应的代码注释：

1. 初始化：设置左右指针left和right，分别初始化为-1和m * n，其中m是矩阵的行数，n是矩阵的列数。right设置为m * n是因为这是矩阵中元素的总数。

   const m = matrix.length, n = matrix[0].length;
   let left = -1, right = m * n;
   

2. 二分查找循环：使用while循环进行二分查找，直到left和right相差1。

   while (left + 1 < right) {
       // ...
   }
   

3. 计算中点：在每次循环中，计算当前查找区间的中点mid。

   const mid = Math.floor((left + right) / 2);
   

4. 转换为一维索引：将中点mid转换成二维索引，即matrix[Math.floor(mid / n)][mid % n]。这里Math.floor(mid / n)得到行索引，mid % n得到列索引。

   const x = matrix[Math.floor(mid / n)][mid % n];
   

5. 比较和调整区间：比较target与x的值。
   • 如果x等于target，则返回true。
   • 如果x小于target，则将left设置为mid。
   • 如果x大于target，则将right设置为mid。

   if (x === target) {
       return true;
   }
   if (x < target) {
       left = mid;
   } else {
       right = mid;
   }
   

6. 返回结果：如果循环结束还没有找到target，则返回false。

   return false;
   

   这个算法的时间复杂度是O(log(m*n))，因为它本质上是在一个长度为m*n的一维数组上进行二分查找。

宇宙级优化

这个算法的思路是从矩阵的右上角开始，利用矩阵的行和列都是有序的性质来逐步缩小搜索范围。下面是算法的步骤和对应的代码注释：

1. 初始化：设置两个变量i和j，分别初始化为矩阵的起始行和终止列，即i = 0, j = n - 1。

   const m = matrix.length, n = matrix[0].length;
   let i = 0, j = n - 1;
   

2. 循环搜索：使用while循环进行搜索，直到超出矩阵的边界。

   while (i < m && j >= 0) {
       // ...
   }
   

3. 比较和调整搜索范围：在每次循环中，比较当前元素matrix[i][j]与目标值target。
   • 如果当前元素等于目标值，直接返回true。
   • 如果当前元素小于目标值，说明当前行剩余的元素都小于目标值，因此排除当前行，i++。
   • 如果当前元素大于目标值，说明当前列剩余的元素都大于目标值，因此排除当前列，j--。

   if (matrix[i][j] === target) {
       return true;
   }
   if (matrix[i][j] < target) {
       i++;
   } else {
       j--;
   }
   

4. 返回结果：如果循环结束还没有找到target，则返回false。

   return false;
   

   这个算法的时间复杂度是O(m+n)，因为它最多只需要遍历矩阵的一行和一列。这是一个非常高效的搜索方法，特别是对于大型矩阵。

暴力

var searchMatrix = function (matrix, target) {
    for (let i = 0; i < matrix.length; i++) {
        const row = matrix[i];
        if (search(row, target)) return true;
    }
    return false
};

function search(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const mid = (left + right) >>> 1;
        if (arr[mid] === target) return true;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1
        }
    }
    return false
}

初级优化

var searchMatrix = function (matrix, target) {
    let top = 0;
    let bottom = matrix.length - 1;
    let row;

    // 首先确定目标可能在的行
    while (top <= bottom) {
        let mid = (top + bottom) >>> 1;
        if (matrix[mid][0] <= target && target <= matrix[mid][matrix[mid].length - 1]) {
            row = mid;
            break;
        } else if (matrix[mid][0] > target) {
            bottom = mid - 1;
        } else {
            top = mid + 1;
        }
    }

    // 如果找到了可能的行，再在该行中二分查找目标值
    if (row !== undefined) {
        let left = 0;
        let right = matrix[row].length - 1;
        while (left <= right) {
            let mid = (left + right) >>> 1;
            if (matrix[row][mid] === target) return true;
            else if (matrix[row][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
    }

    return false;
};

国家级优化

var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let left = -1, right = m * n;
    while (left + 1 < right) {
        const mid = Math.floor((left + right) / 2);
        const x = matrix[Math.floor(mid / n)][mid % n];
        if (x === target) {
            return true;
        }
        if (x < target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return false;
};

世界级优化

var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let i = 0, j = n - 1;
    while (i < m && j >= 0) { // 还有剩余元素
        if (matrix[i][j] === target) {
            return true; // 找到 target
        }
        if (matrix[i][j] < target) {
            i++; // 这一行剩余元素全部小于 target，排除
        } else {
            j--; // 这一列剩余元素全部大于 target，排除
        }
    }
    return false;
};

寻找峰值（中）

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

解题思路

最大值

直接查找最大值的位置，最大值必定峰值。

二分查找

1. 初始化左右指针：l 初始化为 0，r 初始化为 nums.length - 1。这两个指针用来定义当前搜索的区间。
2. 二分查找：使用一个 while 循环，只要 l < r，就执行以下步骤：
   • 计算中间位置 mid：使用 (l + r) >> 1 来找到中间位置的索引。这里使用算术右移是因为数组索引不能是负数，而且 l 和 r 都是正数。
   • 比较中间元素与其右侧元素：
     • 如果 nums[mid] > nums[mid + 1]，说明峰值元素在中间元素的左侧或者在中间元素本身（因为中间元素比它右侧的元素大），所以将 r 设置为 mid。
     • 如果 nums[mid] <= nums[mid + 1]，说明峰值元素在中间元素的右侧，所以将 l 设置为 mid + 1。
3. 返回结果：当 l 和 r 相等时，循环结束。此时 l 或 r 指向的元素即为峰值元素，因为算法保证了峰值元素一定在 l 或 r 指向的位置。

这个算法利用了数组的一个特性：峰值元素至少有一侧是严格下降的。通过比较中间元素和其右侧元素，算法可以判断出峰值元素在哪一侧，并相应地调整搜索区间。最终，l 和 r 会收敛到峰值元素的位置。

最大值

var findPeakElement = function(nums) {
   const max =  Math.max(...nums);
   return nums.findIndex(i => i === max)
};

二分查找

var findPeakElement = function (nums) {
    let l = 0, r = nums.length - 1;
    while (l < r) {
        const mid = (l + r) >> 1;
        // 因为题目中明确过没有相等的值，所以直接大于即可
        if (nums[mid] > nums[mid + 1]) r = mid;
        else l = mid + 1;
    }
    return l;
};

搜索旋转排序数组(中)

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解题思路

当然可以。这个算法是在一个旋转排序数组中搜索一个特定值 target 的位置。旋转排序数组是指原数组经过旋转（例如，[0,1,2,4,5,6,7] 变为 [4,5,6,7,0,1,2]）后形成的数组。算法的基本思路如下：

1. 初始化左右指针：L 初始化为 0，R 初始化为 nums.length - 1。这两个指针用来定义当前搜索的区间。
2. 二分查找：使用一个 while 循环，只要 L <= R，就执行以下步骤：
   • 计算中间位置 mid：使用 (L + R) >>> 1 来找到中间位置的索引。
   • 检查中间元素是否等于 target：
     • 如果 nums[mid] === target，返回 mid，搜索成功。
   • 判断哪一半数组是有序的：
     • 如果 nums[mid] < nums[R]，则右半段 [mid, R] 是有序的。
     • 如果 nums[mid] > nums[R]，则左半段 [L, mid] 是有序的。
   • 根据 target 是否在有序区间内来调整搜索范围：
     • 如果 target 在有序区间内，调整 L 或 R 来缩小搜索范围。
     • 如果 target 不在有序区间内，调整另一侧的指针。
3. 返回结果：如果找到 target，返回其索引；如果循环结束仍未找到，返回 -1。

这个算法的关键在于利用旋转排序数组的特性：数组被分为两部分，其中一部分是有序的。通过比较中间元素和最右侧元素，可以确定哪一半是有序的，然后根据 target 是否在这个有序区间内来调整搜索范围。这样，每次循环都可以排除一半的搜索空间，从而实现高效搜索。

var search = function (nums, target) {
    let L = 0;
    let R = nums.length - 1;
    while (L <= R) {
        const mid = (L + R) >>> 1;
        if (nums[mid] === target) return mid;
        // 如果中间数小于最右边数，则右半段是有序的
        // 如果中间数大于最右边数，则左半段是有序的
        if (nums[mid] < nums[R]) {
            // 判断target是否在(mid, end]之间
            if (nums[mid] < target && target <= nums[R]) {
                // 如果在，则中间数右移即start增大
                L = mid + 1;
            } else {
                // 如果不在，则中间数左移即end减小
                R = mid - 1;
            }
        } else {
            // [start, mid)
            if (nums[L] <= target && target < nums[mid]) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
    }
    return -1;
};

在排序数组中查找元素的第一个和最后一个位置（中）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

二分法解析

1. lowerBound函数的使用：算法中使用了lowerBound函数来寻找目标值的起始位置。这个函数实际上是寻找第一个大于或等于目标值的元素的位置。如果目标值存在，它将返回目标值在数组中的第一个位置；如果不存在，它将返回可以插入目标值的位置。
2. 寻找结束位置：算法中，寻找结束位置的方法是调用lowerBound函数并传入target + 1，然后减去1。这种方法是利用了lowerBound函数的特性：它总是返回第一个大于或等于给定值的元素的索引。因此，lowerBound(nums, target + 1)将返回第一个大于target的元素的索引，减去1后就是target的最后一个位置的索引。
3. 返回值处理：在您的算法中，如果start位置不是目标值或者start超出了数组长度，就直接返回[-1, -1]。这和我之前的算法中检查left和right位置是否为目标值的方法相似。

findIndex

var searchRange = function (nums, target) {
    const left = nums.findIndex(i => i === target);
    if (left === -1) return [-1, -1];
    let right = left;
    while (right < nums.length && nums[right] === target) {
        right++;
    }
    return [left, right - 1]; // right - 1是因为while循环会在不是目标值的地方停止
};

二分查找

var searchRange = function (nums, target) {
    const start = lowerBound(nums, target); // 选择其中一种写法即可
    if (start === nums.length || nums[start] !== target) {
        return [-1, -1]; // nums 中没有 target
    }
    const end = lowerBound(nums, target + 1) - 1;
    return [start, end];
};

// 闭区间写法
var lowerBound = function (nums, target) {
    let left = 0, right = nums.length - 1; // 闭区间 [left, right]
    while (left <= right) { // 区间不为空
        const mid = (left + right) >>> 1;
        if (nums[mid] < target) {
            left = mid + 1; // 范围缩小到 [mid+1, right]
        } else {
            right = mid - 1; // 范围缩小到 [left, mid-1]
        }
    }
    return left;
}

寻找旋转排序数组中的最小值(中)

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/698479/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-5irwp

var findMin = function(nums) {
    let L = 0; // 初始化左指针
    let R = nums.length - 1; // 初始化右指针
    while(L < R) { // 当左指针小于右指针时，继续查找
        const mid = (L + R) >>> 1; // 计算中间位置，使用无符号右移避免整数溢出
        if(nums[mid] > nums[R]) { // 如果中间位置的值大于最右侧的值
            L = mid + 1; // 最小值在中间位置的右侧，调整左指针
        } else { // 否则
            R = mid; // 最小值在中间位置或其左侧，调整右指针
        }
    }
    return nums[L]; // 返回最小值
};

寻找两个正序数组的中位数（难）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5 

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

解题思路

暴力法

先合并再排序

二分法

1. 确定较小的数组：为了简化问题，我们总是确保 nums1 是较短的数组。如果 nums1 比 nums2 长，我们就交换它们。
2. 二分搜索：在 nums1 中使用二分搜索确定一个分割点 i。由于 nums1 和 nums2 的总长度是 m + n，我们可以计算出在 nums2 中的对应分割点 j = halfLen - i，其中 halfLen = (m + n + 1) / 2。
3. 调整分割点：我们需要确保 nums1 的左半部分和 nums2 的左半部分中的所有元素都小于或等于右半部分的所有元素。如果 nums1[i - 1] > nums2[j]，说明 i 太大，我们需要减小 i；如果 nums2[j - 1] > nums1[i]，说明 i 太小，我们需要增大 i。
4. 找到中位数：一旦我们找到了正确的分割点，中位数就是左边最大元素和右边最小元素的平均值（如果总数是偶数）或左边最大元素（如果总数是奇数）。

暴力

var findMedianSortedArrays = function (nums1, nums2) {
    const arr = [...nums1, ...nums2].sort((a,b) => a - b);
    const mid = (arr.length - 1) >>> 1;
    console.log(arr.length % 2)
    if (arr.length % 2) return  arr[mid]
    return (arr[mid] + arr[mid + 1]) / 2
};

二分法

var findMedianSortedArrays = function(nums1, nums2) {
    // 确保 nums1 是较短的数组，这样可以减少二分搜索的次数
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    const m = nums1.length;
    const n = nums2.length;
    let imin = 0, imax = m;
    const halfLen = Math.floor((m + n + 1) / 2);

    // 二分搜索在 nums1 中找到合适的分割点 i
    while (imin <= imax) {
        const i = Math.floor((imin + imax) / 2);
        const j = halfLen - i;

        // 检查分割点是否正确
        // 如果 nums1[i - 1] > nums2[j]，说明 i 太大，需要减小
        if (i < imax && nums2[j - 1] > nums1[i]) {
            imin = i + 1;
        }
        // 如果 nums2[j - 1] > nums1[i - 1]，说明 i 太小，需要增大
        else if (i > imin && nums1[i - 1] > nums2[j]) {
            imax = i - 1;
        }
        // 分割点正确，计算中位数
        else {
            // 找到左边的最大值
            let maxLeft = 0;
            if (i === 0) { maxLeft = nums2[j - 1]; }
            else if (j === 0) { maxLeft = nums1[i - 1]; }
            else { maxLeft = Math.max(nums1[i - 1], nums2[j - 1]); }

            // 如果总数是奇数，返回左边的最大值
            if ((m + n) % 2 === 1) {
                return maxLeft;
            }

            // 找到右边的最小值
            let minRight = 0;
            if (i === m) { minRight = nums2[j]; }
            else if (j === n) { minRight = nums1[i]; }
            else { minRight = Math.min(nums1[i], nums2[j]); }

            // 返回左边最大值和右边最小值的平均值
            return (maxLeft + minRight) / 2;
        }
    }
};