【LeetCode Hot100 二分查找】搜索插入位置、搜索二维矩阵、搜索旋转排序数 ...

搜索插入位置

给定一个排序数组和一个目的值，在数组中找到目的值，并返回其索引。如果目的值不存在于数组中，返回它将会被按序次插入的位置。
请必须利用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
代码：
闭区间解法

1. class Solution {
2.     public int searchInsert(int[] nums, int target) {
3.         int left = 0, right = nums.length - 1;
4.         while(left <= right) {
5.             int mid = left + (right - left) / 2;
6.             if (nums[mid] == target) {
7.                 return mid;
8.             } else if (nums[mid] > target) {
9.                 right = mid - 1;
10.             } else {
11.                 left = mid + 1;
12.             }
13.         }
14.         return left;
15.     }
16. }

复制代码

搜索二维矩阵

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

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

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

思绪
把该二维矩阵设想成一个一维的有序数组，那么在该一维数组的第                                    i                              i                  i 个位置的数可以用二维矩阵 ( m 行 n 列) 体现，即在                                    i                         /                         n                              i/n                  i/n 行，                                   i                         %                         n                              i\%n                  i%n 列.
代码
在上一题的底子上修改代码：

1. class Solution {
2.     public boolean searchMatrix(int[][] matrix, int target) {
3.         int m = matrix.length;
4.         int n = matrix[0].length;
5.         int left = 0, right = m*n-1;
6.         while(left <= right) {
7.             int mid = left + (right - left) / 2;
8.             int val = matrix[mid/n][mid%n];
9.             if (val == target) {
10.                 return true;
11.             } else if(val < target) {
12.                 left = mid + 1;
13.             } else {
14.                 right = mid - 1;
15.             }
16.         }
17.         return false;
18.     }
19. }

复制代码

在排序数组中查找元素的第一个和末了一个位置

给你一个按照非递减序次排列的整数数组 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]
思绪
用两次二分查找分别找左边界和有边界
第一次二分法找左边界，第二次二分法找右边界
代码
先初始化左边界有边界为 -1

1. class Solution {
2.     public int[] searchRange(int[] nums, int target) {
3.         int left = 0, right = nums.length - 1;
4.         int leftBoard = -1, rightBoard = -1;
5.         // 寻找左边界
6.         while(left <= right) {
7.             int mid = left + (right - left) / 2;
8.             if (nums[mid] == target) {
9.                 leftBoard = mid;
10.                 right = mid - 1;  // 找到之后 在 mid 的左边区间继续找，直到找到最左边的边界
11.             } else if(nums[mid] < target) {
12.                 left = mid + 1;
13.             } else {
14.                 right = mid - 1;
15.             }
16.         }
17.         left = 0;
18.         right = nums.length - 1;
19.         // 寻找右边界
20.         while(left <= right) {
21.             int mid = left + (right - left) / 2;
22.             if (nums[mid] == target) {
23.                 rightBoard = mid;
24.                 left = mid + 1;
25.             } else if(nums[mid] < target) {
26.                 left = mid + 1;
27.             } else {
28.                 right = mid - 1;
29.             }
30.         }
31.         return new int[]{leftBoard, rightBoard};
32.     }
33. }

复制代码

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

已知一个长度为 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 次得到输入数组。
思绪
设 x=nums[mid] 是现在二分取到的数。
我们须要判定 x 和数组最小值的位置关系，谁在左边，谁在右边？
把 x 与末了一个数 nums[n−1] 比巨细：

• 如果 x>nums[n−1]，那么可以推出以下结论：
  
  
  
  • nums 一定被分成左右两个递增段；
    
  • 第一段的所有元素均大于第二段的所有元素；
    
  • x 在第一段。
    
  • 最小值在第二段。
    
  • 所以 x 一定在最小值的左边。
    
  
  
• 如果 x≤nums[n−1]，那么 x 一定在第二段。（大概 nums 就是递增数组，此时只有一段。）
  
  
  
  • x 要么是最小值，要么在最小值右边。
    
  
  

所以，只须要比较 x 和 nums[n−1] 的巨细关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。
代码

1. class Solution {
2.     public int findMin(int[] nums) {
3.         int n = nums.length;
4.         int left = 0, right = n - 2;
5.         while(left <= right) {
6.             int mid = left + (right - left) / 2;
7.             if (nums[mid] > nums[n - 1]) {
8.                 left = mid + 1;
9.             } else {
10.                 right = mid - 1;
11.             }
12.         }
13.         return nums[left];
14.     }
15. }

复制代码

搜索旋转排序数组

整数数组 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) 的算法办理此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
思绪
利用上一题的思绪，先找到该旋转排序数组的最小值的位置，然后根据 target 和 旋转的位置（旋转排序数组的末了一个数）的巨细进行比较，判定是在左边查找还是在右边查找。
代码

1. class Solution {
2.     public int search(int[] nums, int target) {
3.         int min = findMin(nums);  // 先找到最小值的下标
4.         int n = nums.length;
5.         if (target == nums[n -1]) {
6.             return n - 1;   // 相等的话直接返回
7.         } else if (target > nums[n-1]) {
8.             return searchTarget(nums, target, 0, min - 1);  // 在左边查找
9.         } else {
10.             return searchTarget(nums, target, min, n - 2);  // 在右边查找
11.         }
12.     }
13.         // 查找最小值下标
14.     public int findMin(int[] nums) {
15.         int n = nums.length;
16.         int left = 0, right = n - 2;
17.         while( left <= right) {
18.             int mid = left + (right - left) / 2;
19.             if (nums[mid] > nums[n - 1]) {
20.                 left = mid + 1;
21.             } else {
22.                 right = mid - 1;
23.             }
24.         }
25.         return left;
26.     }
27.         // 二分查找
28.     public int searchTarget(int[] nums, int target, int left, int right) {
29.         int n = nums.length;
30.         while(left <= right) {
31.             int mid = left + (right - left) / 2;
32.             if (nums[mid] == target) {
33.                 return mid;
34.             } else if (nums[mid] > target) {
35.                 right = mid - 1;
36.             } else {
37.                 left = mid + 1;
38.             }
39.         }
40.         return -1;
41.     }
42. }

复制代码

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

给定两个巨细分别为 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 是较短的数组
  

• 由于我们要在较短的数组上进行二分查找，为了减少计算复杂度，我们首先确保 nums1 的长度小于或等于 nums2。如果 nums1 的长度大于 nums2，我们互换这两个数组。
  
• 如许做的目的是保证二分查找的次数最小化，最大化效率。
  

• 分割数组
  

• 我们的目的是将两个数组分割成左右两部门，使得合并后的两个部门的元素个数相同，大概左边多一个元素（如果总长度是奇数）。具体来说，假设 nums1 的长度是 n，nums2 的长度是 m，则：
  
  
  
  • 左边部门的元素个数应为 (n + m + 1) / 2，这个值可以保证左边部门最多比右边部门多一个元素（当总长度是奇数时）。
    
  • 右边部门的元素个数为 n + m - (n + m + 1) / 2。
    
  
  

• 二分查找
  

• 在 nums1 上执行二分查找，假设当前查找的分割位置是 partition1，那么 nums1 的左边部门就是 nums1[0]…nums1[partition1-1]，右边部门是 nums1[partition1]…nums1[n-1]。
  
• 同样地，nums2 的分割位置 partition2 可以通过以下公式计算：
                                           p                            a                            r                            t                            i                            t                            i                            o                            n                            2                            =                            (                            n                            +                            m                            +                            1                            )                            /                            2                            −                            p                            a                            r                            t                            i                            t                            i                            o                            n                            1                                  partition2= (n+m+1)/2 −partition1                     partition2=(n+m+1)/2−partition1
  这个公式确保了左边部门的总元素个数为 (n + m + 1) / 2。
  

• 确保分割符合条件
  

• 为了保证左边部门的所有元素都小于或等于右边部门的所有元素，我们须要查抄：
  
  
  
  • nums1[partition1 - 1] <= nums2[partition2]（nums1 左边的最大值小于 nums2 右边的最小值）。
    
  • nums2[partition2 - 1] <= nums1[partition1]（nums2 左边的最大值小于 nums1 右边的最小值）。
    如果这些条件成立，说明我们找到了合适的分割位置。
    
  
  

• 计算中位数
  

• 如果两个数组的总长度是奇数，中位数就是左边部门的最大值，max(nums1[partition1 - 1], nums2[partition2 - 1])。
  
• 如果两个数组的总长度是偶数，中位数是左边部门的最大值和右边部门的最小值的平均值：
                                           m                            e                            d                            i                            a                            n                            =                            (                            m                            a                            x                            (                            n                            u                            m                            s                            1                            [                            p                            a                            r                            t                            i                            t                            i                            o                            n                            1                            −                            1                            ]                            ,                            n                            u                            m                            s                            2                            [                            p                            a                            r                            t                            i                            t                            i                            o                            n                            2                            −                            1                            ]                            )                            +                            m                            i                            n                            (                            n                            u                            m                            s                            1                            [                            p                            a                            r                            t                            i                            t                            i                            o                            n                            1                            ]                            ,                            n                            u                            m                            s                            2                            [                            p                            a                            r                            t                            i                            t                            i                            o                            n                            2                            ]                            )                            )                            /                            2                                  median = (max(nums1[partition1−1],nums2[partition2−1])+min(nums1[partition1],nums2[partition2])) / 2                     median=(max(nums1[partition1−1],nums2[partition2−1])+min(nums1[partition1],nums2[partition2]))/2
  

• 二分查找的调解
  

• 如果不满足条件，意味着 partition1 须要调解：
  
  
  
  • 如果 nums1[partition1 - 1] > nums2[partition2]，则须要将 partition1 向左移，即减小 partition1。
    
  • 如果 nums2[partition2 - 1] > nums1[partition1]，则须要将 partition1 向右移，即增大 partition1。
    
  
  

• 边界条件
  

• 对于数组的边界，我们利用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 来处理数组分割的边界环境。比方，如果 partition1 为 0，意味着 nums1 左边部门没有元素，我们将 maxLeft1 设置为 Integer.MIN_VALUE；如果 partition1 为 n，意味着 nums1 右边部门没有元素，我们将 minRight1 设置为 Integer.MAX_VALUE。
  

代码

1. public class Solution {
2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3.         // 保证 nums1 是较短的数组
4.         if (nums1.length > nums2.length) {
5.             int[] temp = nums1;
6.             nums1 = nums2;
7.             nums2 = temp;
8.         }
10.         int n = nums1.length;
11.         int m = nums2.length;
13.         // 在 nums1 上进行二分查找
14.         int left = 0, right = n;
16.         while (left <= right) {
17.             int partition1 = (left + right) / 2;
18.             int partition2 = (n + m + 1) / 2 - partition1;
20.             // 获取 nums1 和 nums2 中的元素
21.             int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
22.             int minRight1 = (partition1 == n) ? Integer.MAX_VALUE : nums1[partition1];
24.             int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
25.             int minRight2 = (partition2 == m) ? Integer.MAX_VALUE : nums2[partition2];
27.             // 检查是否找到合适的分割位置
28.             if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
29.                 // 如果数组长度是奇数
30.                 if ((n + m) % 2 == 1) {
31.                     return Math.max(maxLeft1, maxLeft2);
32.                 } else {
33.                     // 如果数组长度是偶数
34.                     return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
35.                 }
36.             } else if (maxLeft1 > minRight2) {
37.                 // 如果 maxLeft1 太大，调整左边界
38.                 right = partition1 - 1;
39.             } else {
40.                 // 如果 maxLeft2 太大，调整右边界
41.                 left = partition1 + 1;
42.             }
43.         }
45.         return 0.0;
46.     }
47. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。