【LeetCode HOT 100】具体题解之二分查找篇
35 搜索插入位置35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按次序插入的位置。
请必须利用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = , target = 5
输出: 2
示例 2:
输入: nums = , target = 2
输出: 1
示例 3:
输入: nums = , target = 7
输出: 4
提示:
[*]1 <= nums.length <= 104
[*]-104 <= nums <= 104
[*]nums 为 无重复元素 的 升序 分列数组
[*]-104 <= target <= 104
思路
一般利用二分查找算法必要满意以下两个条件
[*]用于查找的内容有序
[*]查找的数量只能是一个，而不是多个
举个例子，在一个有序且无重复元素的数组中，例如nums=中查找元素16，如许就可以利用二分查找。
二分查找中，目标元素的查找区间定义十分重要。我们要确定查找的范围。重要有以下两种方式
[*] 左闭右闭 （此时while循环为while(left<=right) ）
[*][left,right) 左闭右开（此时while循环为while(left<right)）
[*]这两种方式的实现会在while循环的判定，以及对right的更新上存在肯定的区别。在下面会举行具体说明。
用二分查找，查找区间为 左闭右闭的操纵查找步骤如下：
nums=
下标 = 0,1,2,3,4, 5 , 6, 7
[*] l = 0, r = nums.length -1 = 7
[*] mid = (l+r)/2 = 3
[*] 比力nums = 8和target = 16 的大小
[*] nums>target
说明区间内的全部元素都大于target,此时要去区间中查找，更新右界限right
right = mid -1;
[*] nums<target （8<16,说明要在中找）
说明区间内的全部元素都小于target,此时要去区间中查找,更新左界限left
left = mid + 1
[*] nums==target ,直接return mid
不断循环1，2，3直到找到为止，若循环完都没有return说明查找元素在数组中不存在
代码(左闭右闭)
class Solution {
public int searchInsert(int[] nums, int target) {
/**
二分查找，查找区间写为
*/
int l = 0,r = nums.length-1;
while(l <= r){
int mid = l + (r-l)/2;
if(nums>target){
//注意这里，是将r 更新为mid - 1
r = mid-1;
}else if(nums<target){
l = mid +1;
}else if(nums==target){
return mid;
}
}
return l;
}
}
代码(左闭右开)
class Solution {
public int searchInsert(int[] nums, int target) {
/**
二分查找，查找区间写为
*/
int l = 0,r = nums.length; //这里r是nums.length,因为查找范围不包括nums
while(l < r){ //这里是l<r,因为查找范围为[l,r)
int mid = l + (r-l)/2;
if(nums>target){
r = mid; //这里r= mid,因为查找范围不包括r
}else if(nums<target){
l = mid +1;
}else if(nums==target){
return mid;
}
}
return l;
}
}
74 搜索二维矩阵
74. 搜索二维矩阵
给你一个满意下述两条属性的 m x n 整数矩阵：
[*]每行中的整数从左到右按非严格递增次序分列。
[*]每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
https://i-blog.csdnimg.cn/direct/2dc4fb0524b944e094d0c32a4834c2fc.png
输入：matrix = [,,], target = 3
输出：true
示例 2：
https://img-blog.csdnimg.cn/img_convert/7c6cb46013000a8e3c94fc4819a4f673.jpeg
输入：matrix = [,,], target = 13
输出：false
思路
挺简单的，遍历每一行，获取每一行的第一个元素和最后一个元素，判定target是否在该行中。若在该行中，则利用二分查找，若不在，则继承遍历下一行。
代码(左闭右闭)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix.length;
for(int i = 0;i<m;i++){
if(target>=matrix && target <=matrix){
int l = 0,r = n-1;
while(l<=r){
int mid = l + (r-l)/2;
if(matrix>target){
r = mid -1;
}else if(matrix<target){
l = mid + 1;
}else if(matrix==target){
return true;
}
}
}
}
return false;
}
}
34 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减次序分列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和竣事位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = , target = 8
输出：
示例 2：
输入：nums = , target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
[*]0 <= nums.length <= 105
[*]-109 <= nums <= 109
[*]nums 是一个非递减数组
[*]-109 <= target <= 109
思路
二分查找的变体。
本题中会存在重复的元素，所以必要用二分查找来找到某个元素在数组中第一次出现的位置。将二分查找算法写成函数lowerBound，该函数会找到target第一次出现的位置。调用两次该方法，第一次查找target，第二次查找target+1，如许就能乐成返回目标在数组中的开始位置和竣事位置。
我们必要考虑界限情况。如果数组为空，大概全部数都<target,那么会返回nums.length，因此lowerBound返回值为nums.length时，直接返回-1，-1，此外还必要判定lowerBound返回的下标在数组中对应的值是否即是target。
lowerBound如何实现呢，和二分查找的差别在于更新右界限，不管nums <target还是nums=target , 都会一直往左找，直到找到该元素第一次出现的位置。
if(numd<target){
l = mid + 1;
}else{
r = mid - 1; //这里不管nums <target还是nums=target , 都会一直往左找，直到找到第一个
}
代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = lowerBound(nums,target);
if(start == nums.length || nums !=target){
return new int[]{-1,-1};
}
int end = lowerBound(nums,target+1)-1;
return new int[]{start,end};
}
/**
lowerBound返回 [最小的]满足nums>=target的i ，如何实现呢
也可以理解为找到target第一次出现的位置。
如果数组为空，或者所有数都<target,那么会返回nums.length
if(numd<target){
l = mid + 1;
}else{
r = mid - 1; //这里不管nums <target还是nums=target , 都会一直往左找，直到找到第一个
}
*/
public int lowerBound(int[] nums,int target){
int l = 0,r = nums.length-1;
while(l<=r){
int mid = l + (r-l)/2;
if(nums>target){
r = mid - 1;
}else if(nums<target){
l = mid + 1;
}else if(nums==target){
r = mid - 1;
}
}
return l;
}
}
33 搜索旋转排序数组
33. 搜索旋转排序数组
整数数组 nums 按升序分列，数组中的值 互不相同 。
在通报给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上举行了 旋转，使数组变为 , nums, ..., nums, nums, nums, ..., nums]（下标 从 0 开始 计数）。例如， 在下标 3 处经旋转后可能变为 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = , target = 0
输出：4
示例 2：
输入：nums = , target = 3
输出：-1
示例 3：
输入：nums = , target = 0
输出：-1
提示：
[*]1 <= nums.length <= 5000
[*]-104 <= nums <= 104
[*]nums 中的每个值都 独一无二
[*]题目数据保证 nums 在预先未知的某个下标上举行了旋转
[*]-104 <= target <= 104
思路
题目分析
本题是在一个可能经过旋转的有序数组中查找给定目标值的问题。由于数组经过旋转，所以它被分为了两个部门，一部门是有序的，另一部门是无序的。我们必要利用这个特点来举行高效的查找。
二分查找，每次查找肯定能有一部门是有序的，一部门是无序的
判定target在哪部门，若在有序的部门则直接二分查找，若在无序的部门就继承切割为有序和无序
解题思路
[*]初始化指针
[*]首先，定义两个指针 l 和 r，分别指向数组的首尾位置，表现当前搜索的区间。
[*]循环查找
[*]进入一个循环，只要 l 不高出 r，就继承查找。
[*]在每次循环中，计算当前区间的中间位置 mid，即 mid = l + (r - l)/2。
[*]情况判定
[*]如果 nums 即是目标值 target，说明找到了目标，直接返回 mid。
[*]如果 nums 不即是目标值，必要判定当前的中间位置处于哪个区间（有序区间还是无序区间）。
[*]如果nums <= nums，说明左边是有序区间：
[*]如果目标值 target 在这个有序区间内（即 nums <= target && nums >= target），那么更新 r 为 mid - 1，继承在有序区间中查找。
[*]如果目标值不在这个有序区间内，说明在无序区间中，此时更新 l 为 mid + 1。
[*]如果nums <= nums，说明右边是有序区间：
[*]如果目标值 target 在这个有序区间内（即 nums <= target && nums >= target），那么更新 l 为 mid + 1，继承在有序区间中查找。
[*]如果目标值不在这个有序区间内，说明在无序区间中，此时更新 r 为 mid - 1。
[*]返回效果
[*]如果循环竣事后还没有找到目标值，说明目标值不在数组中，返回 -1。
三、算法复杂度分析
[*]时间复杂度：
[*]由于每次循环都将搜索区间缩小一半，所以时间复杂度为O(logn) ，其中 n 是数组的长度。
[*]空间复杂度：
[*]算法只利用了几个额外的变量，不随输入规模增长而增长，所以空间复杂度为O(1) 。
代码
class Solution {
public int search(int[] nums, int target) {
/**
二分查找，每次查找一定能有一部分是有序的，一部分是无序的
判断target在哪部分，若在有序的部分则直接二分查找，若在无序的部分就继续切割为有序和无序
*/
int l = 0,r = nums.length-1;
while(l<=r){
int mid = l + (r-l)/2;
//1.如果当前数等于target，直接返回
if(nums==target){
return mid;
}else if(nums<=nums){
//2.左边是顺序区间
//2.1判断当前元素是否在顺序区间中,若在顺序区间中，更新r为mid-1，继续在顺序区间中查找
if(nums<= target && nums>=target){
r = mid - 1;
}else{//不在顺序区间中，在无序区间中
l = mid + 1;
}
}else if(nums<=nums){
//3.右边是顺序区间
//3.1 判断当前元素是否在顺序区间中
//3.2 若在顺序区间中，更新l 为mid + 1,继续在顺序区间中查找
if(nums<=target && nums>=target){
l = mid + 1;
}else{
r = mid - 1; //在无需区间中查找
}
}
}
return -1;
}
}
153 探求旋转排序数组中的最小值
153. 探求旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序分列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = 在变革后可能得到：
[*]若旋转 4 次，则可以得到
[*]若旋转 7 次，则可以得到
注意，数组 , a, a, ..., a] 旋转一次 的效果为数组 , a, a, a, ..., a] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序分列的数组，并按上述情形举行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums =
输出：1
解释：原数组为 ，旋转 3 次得到输入数组。
示例 2：
输入：nums =
输出：0
解释：原数组为 ，旋转 3 次得到输入数组。
示例 3：
输入：nums =
输出：11
解释：原数组为 ，旋转 4 次得到输入数组。
提示：
[*]n == nums.length
[*]1 <= n <= 5000
[*]-5000 <= nums <= 5000
[*]nums 中的全部整数 互不相同
[*]nums 原来是一个升序排序的数组，并举行了 1 至 n 次旋转
思路
实现思路
[*]利用二分查找的思想，通过比力中间元素和数组末尾元素的大小关系来确定最小值所在的区间，不断缩小区间范围，直到找到最小值。
[*]由于数组经过旋转后被分为了两个部门，一部门是原升序数组的某个子区间，另一部门是旋转后的子区间，最小值就在这两个区间的交界处。通过比力中间元素和末尾元素，可以确定当前中间元素处于哪个子区间，从而缩小查找范围。
具体实现步骤
[*]初始化指针
[*]定义两个指针 l 和 r，分别指向数组的首和尾位置，表现当前搜索的区间范围。初始时，l = 0，r = nums.length - 1。
[*]进入循环
[*]进入一个循环，只要 l 小于即是 r，就继承查找。
[*]计算中间位置
[*]在每次循环中，计算当前区间的中间位置 mid，即 mid = l + (r - l)/2。
[*]情况判定与区间调解
[*]如果nums <= nums：
[*]说明 为翻转后的递增区间，此时最小值肯定在 中，所以将 r 更新为 mid - 1。
[*]如果nums > nums：
[*]说明 为未翻转的递增区间，那最小值肯定在 中，所以将 l 更新为 mid + 1。
[*]如果nums == nums：
[*]说明无法确定最小值在哪个区间，但由于最终要返回 l，所以将 r 更新为 mid - 1，缩小搜索范围。
[*]返回效果
[*]循环竣事后，l 指向的位置就是数组中的最小值，返回 nums。
算法复杂度分析
[*]时间复杂度：
[*]由于每次循环都将搜索区间缩小一半，所以时间复杂度为 O(logn)，其中 n 是数组的长度。
[*]空间复杂度：
[*]算法只利用了几个额外的变量，不随输入规模增长而增长，所以空间复杂度为 O(1)。
代码
class Solution {
public int findMin(int[] nums) {
/**
使用nums和nums比
不停的拿中间的数和最后一个数比较，缩小区间，一共有三种情况
nums<nums : 说明为翻转后的递增区间,此时最小值一定在中
nums>nums: 说明为未翻转的递增区间，那最小值一定在中
nums==nums:说明最小值为n-1,因为我们要返回l,所以将r更新为mid-1
不断缩小区间，最终找到最小值返回
*/
int l = 0,r = nums.length-1;
int n = nums.length;
while(l <= r){
int mid = l + (r-l)/2;
if(nums<=nums){
//
r = mid - 1;
}else {
l = mid + 1;
}
}
return nums;
}
}
4 探求两个正序数组的中位数
4. 探求两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = , nums2 =
输出：2.00000
解释：合并数组 = ，中位数 2
示例 2：
输入：nums1 = , nums2 =
输出：2.50000
解释：合并数组 = ，中位数 (2 + 3) / 2 = 2.5
提示：
[*]nums1.length == m
[*]nums2.length == n
[*]0 <= m <= 1000
[*]0 <= n <= 1000
[*]1 <= m + n <= 2000
[*]-106 <= nums1, nums2 <= 106
思路
解题思路
[*]将求两个有序数组的中位数问题转化为求两个数组归并后第k小的数的问题。
[*]利用二分查找的思想，每次排除肯定命量的元素，逐步缩小搜索范围，直到找到第k小的数。
界限情况考虑
[*]当其中一个数组到达界限时：
[*]如果已经到达数组nums1的界限，此时要求的第k小的元素即为nums2开始的第k个，直接返回nums2。
[*]同理，如果已经到达数组nums2的界限，返回nums1。
[*]当k = 1时：
[*]必要找到两个数组中第 1 小的数，直接返回两个数组开头的最小值。
具体实现步骤
[*]求中位数的主方法
[*]首先，计算两个数组的长度m和n。
[*]如果归并后的数组大小为奇数，直接求第(m + n)/2 + 1小的数即可，将效果逼迫转换为double范例后返回。
[*]如果归并后的数组大小为偶数，那么必要求解第(m + n)/2和第(m + n)/2 + 1小的数，然后取平均并返回。
[*]求第k小的数的辅助方法
[*]初始化两个数组的指针index1和index2，分别指向nums1和nums2的起始位置。
[*]进入一个循环，在循环中不断缩小搜索范围，直到找到第k小的数。
[*]在每次循环中，首先判定界限情况：
[*]如果到达nums1的界限，返回nums2。
[*]如果到达nums2的界限，返回nums1。
[*]如果k = 1，返回两个数组开头的较小值。
[*]正常处理时，为了后续比力的方便，先求出A和B的下标，但要注意不能直接index + k/2 - 1，可能会越界，应该利用Math.min(index + k/2, array.length) - 1来计算。
[*]判定nums1和nums2的大小：
[*]如果nums1 > nums2，说明可以排撤除nums2中的部门，更新index2 = index2 + k/2，同时更新k的值为k -= newIndex2 - index2 + 1。
[*]如果nums1 < nums2，可以排撤除nums1中的部门，更新index1 = index1 + k/2，更新k的值为k -= newIndex1 - index1 + 1。
五、算法复杂度分析
[*]时间复杂度：
[*]由于每次循环都将搜索范围缩小一半，所以时间复杂度为O(logn)，其中m和n分别是两个数组的长度。
[*]空间复杂度：
[*]算法只利用了几个额外的变量，不随输入规模增长而增长，所以空间复杂度为O(1)。
代码
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
/**
使用求两个数组中第k小的数来求解中位数。两种情况
1.合并后的数组大小为奇数num，则直接求第 num/2+1 小的数即可
2.合并后的数组大小为偶数num，那么需要求解第 num/2 ，和第num/2+1小的数，然后再取平均
*/
int m = nums1.length,n = nums2.length;
if((m+n)%2!=0){
int mid = getKthElement(nums1,nums2,(m+n)/2+1);
return (double)mid;
}else{
double mid1 = getKthElement(nums1,nums2,(m+n)/2);
double mid2 = getKthElement(nums1,nums2,(m+n)/2+1);
return (mid1+mid2)/2;
}
}
/**
转换为求两个数组中第k小的数，因为时间复杂度需要为O(log(m+n)),因此考虑二分查找的办法。
每次排除都排除k/2个元素。
假设有A,B两个数组，现在要求A,B数组合并后的第k小的数
求A B的值，判断这两个的大小
1.若A > B，说明B中的k/2个数一定不会是第k小的数，所以更新B的下标，排除B
2.反之若A < B 说明A中的k/2个数一定不会是第k小的数，所以更新A的下标，排除A
相等的话，排除A和B都行，这里排除A
在排除A/B的k/2个元素后，我们现在需要在新的数组中找到第k - k/2 小的元素，因此更新k = k-k/2
注意边界条件：
1.假如已经到达A/B数组的边界，以A为例，已经到达数组A的边界
此时要求的第k小的元素即为B开始的第k个，直接返回B,反之则返回A
2.假如k=1，需要找到两个数组中第1小的数，直接返回两个数组开头的最小值
*/
private int getKthElement(int nums1[],int nums2[],int k){
int index1 = 0,index2 = 0;
while(true){
//1.判断边界条件
//1.1 到达数组1的边界,返回数组2中第k小的数
if(index1==nums1.length){
return nums2;
}
//1.2 到达数组2的边界，返回数组1中第k小的数
if(index2==nums2.length){
return nums1;
}
//1.3 k==1，需要找到两个数组中第1小的数,直接取两个数组中index较小的数
if(k==1){
return Math.min(nums1,nums2);
}
//2.正常处理
// 2.1 为了后续比较的方便，先求出A和B的下标
// newIndex1 等价于 A的k/2-newIndex2 等价于B的k/2-1
// 注意，直接index+k/2-1会越界！！！，所以不能这样。
// int newIndex1 = index1 + k/2 - 1;
// int newIndex1 = index2 + k/2 -1;
int newIndex1 = Math.min(index1+k/2,nums1.length)-1;
int newIndex2 = Math.min(index2+k/2,nums2.length)-1;
//2.2 判断A和B的大小，即判断A和B的大小
//2.2.1 nums1 > nums2,可以排除掉nums2中的部分，更新index2 = index2 + k/2,同时更新k的值
if(nums1>nums2){
//（1）更新k的值
k -= newIndex2-index2+1;
//（2）排除掉后，更新index2的值
index2 = newIndex2+1;
}else {
//2.2.2 nums1 < nums2,可以排除掉nums1中的部分，更新index1 = index1 + k/2
// 注意这里等于的情况放在哪里都可以。
//（1）更新k的值
k -= newIndex1 - index1 +1;
//（2）排除掉后，更新index1的值
index1 = newIndex1 +1;
}
// （×）2.2.3 更新k，因为已经排除掉了k/2个元素，现在只需要求k-k/2小的值,
// k = k - k/2;
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]