二分查找相关题目

1.普通版二分查找

普通版的只要注意到区间范围就好，我使用的是左闭右闭方法,注意以下几点就可以。

right = nums.length - 1;
left < = right
right = mid -1;
left = mid +1

牛客链接

二分查找-I_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @param target int整型 * @return int整型*/public int search (int[] nums, int target) {int result = 0;int left = 0 ;int right = nums.length - 1;while(left <= right){int middle = (left + right)/2;if(nums[middle] > target){right = middle - 1 ;}else if(nums[middle] < target){left = middle + 1;}else{return middle;}}
//      未找到目标值return -1;}
}

2.排序数组中查找第一个元素和最后一个元素

力扣链接如下：

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

这个题的关键点在于怎么查找出左边界和右边界，先上一个暴力解法的版本

暴力解法

class Solution {public int[] searchRange(int[] nums, int target) {int left = 0;int right = 0;int temp = 0;for(int i = 0; i < nums.length; i++){if(nums[i] == target){left = i;temp = 1;break;}}for(int j = left; j <nums.length ;j++){if(nums[j] != target){right = j-1;break;}right = j;}if(temp == 1){return new int[]{left,right};}else{return new int[]{-1,-1};}}
}

二分法查找

使用二分查找的方法的话，就是先找到左边界的第一个目标元素，在找到右边界的目标元素，使用两次二分查找即可。

class Solution {public int[] searchRange(int[] nums, int target) {int left = searchLeftBorder(nums,target);int right  = searchRightBorder(nums,target);// 这里要对边界条件进行一个判断if(left <= right && right <= nums.length ){return new int[]{left,right};}return new int[]{-1,-1};}// 获取左边界// 判断左边界就是找到第一个等于target的位置public int searchLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int first = -1;while(left <= right){int mid = (left + right) / 2;if(nums[mid] == target){first = mid;// 因为要获取的是左边界，现在第一个查找出来的也不知道是不是最左的// 所有把二分查找的右边界移到现在查找出来的值的左边right = mid -1;}else if(nums[mid] > target){right = mid -1;}else if(nums[mid] < target){left = mid + 1;}}return first;}// 获取右边界// 就是找到最后一个等于target的位置public int searchRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int last = -1;while(left <= right){int mid = (left + right) / 2;if(nums[mid] == target){last = mid;// 因为要获取的是右边界，现在第一个查找出来的也不知道是不是最右的// 所有把二分查找的左边界移到现在查找出来的值的右边left = mid + 1;}else if(nums[mid] > target){right = mid -1;}else if(nums[mid] < target){left = mid + 1;}}return last;}
}

3.第一个错误版本

力扣链接：

. - 力扣（LeetCode）

这个题目的关键在于理解题意

// 如果一个版本是正确的，那这个版本之前的都是正确的
// 如果一个版本是错误的，那这个版本之后的都是错误的
// 通过二分查找限定范围
// 起始左边为1，右边为n

while循环不能写成left<= right ,因为如果n =1就成死循环了

// 注意 isBadVersion为false时，代表是正确版本

注意到这几点后就和普通的二分查找是一样的了

/* The isBadVersion API is defined in the parent class VersionControl.boolean isBadVersion(int version); */// 如果一个版本是正确的，那这个版本之前的都是正确的
// 如果一个版本是错误的，那这个版本之后的都是错误的
// 通过二分查找限定范围
// 起始左边为1，右边为n
public class Solution extends VersionControl {public int firstBadVersion(int n) {int left = 1;int right = n;// 注意这里不能写 = 号// 因为如果n=1 的话就进入死循环了while(left < right){int mid = left + (right - left) / 2;// 注意 isBadVersion为false时，代表是正确版本// 刚开始直接把题意给理解错误了，导致写反了if(isBadVersion(mid)){// mid是错误版本right = mid -1; }else {
//              mid 是正确版本left = mid + 1;}}return left; }
}

4.寻找两个正序数组的中位数