目录
1.二分查找是干啥的
2. 力扣中的一些练习题
2.1 二分查找
2.2 第一个错误的版本
2.3 搜索插入位置
2.4 在排序数组中查找元素第一个和最后一个位置
2.5 x的平方根
2.6 有效的完全平方数
3.总结一下
1.二分查找是干啥的
二分查找（Binary Search）也叫作折半查找。
是在有序数组中，寻找一个数字，然后返回其对应要求的值，二分查找相比于暴力求解，算法效率是比较高的。
二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。
二分查找的算法思想是
2. 力扣中的一些练习题
2.1 二分查找(两种方法定义 target 是在一个在左闭右闭的区间里，也就是[left, right] )
链接 704. 二分查找 - 力扣（LeetCode）
这个题就是让在数组里找到这个数字，然后返回数字下标
因为力扣中的题是核心代码模式，所以我也就不写如何输入了
第一种写法
定义 target 在一个在左闭右闭的区间里，也就是[left, right] 这个中，
区间的定义决定了二分法的代码应该怎么样写
因为定义在了这个区间中，所以考虑下面两点
循环while结束的条件是什么
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
给left和right赋什么值
if (nums[mid]< target) left 要赋值为 mid + 1，因为当前这个nums[mid]一定不是target，那么接下来要查找的左区间结束下标位置就是 mid + 1
class Solution {
public int search(int[] nums, int target) {
//target定义在左闭右闭的区间里，[left,right]
int left = 0;
int right = nums.length-1;
while(left <= right){
//当left==right，区间[left,right]依然有效，所以用<=
int mid = left + (right-left)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
//target在右区间,所以[mid+1,right]
}else{
//(nums[mid]>target)target在左区间,所以[left,mid-1]
right = mid - 1;
}
}
return -1;
}
}第二种写法
定义 target 在一个在左闭右开的区间里，也就是[left, right) 这个中，
根据二分法的边界处理方式，就有不同的考虑。
因为定义在了这个区间中，所以考虑下面两点
循环while结束的条件是什么
while (left < right) 要使用 <，因为left == right在区间[left, right)是没有意义的
给left和right赋什么值
if (nums[mid] > target) right 更新为 mid，因为当前nums[mid]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为mid，即：下一个查询区间不会去比较nums[mid]
注意看和第一种方法中的图有什么不一样
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
// 定义target在左闭右开的区间里，即：[left, right)
while (left < right) {
//因为left==right的时候，在[left, right)是无效的空间，所以使用<
int mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid;
// target 在左区间，在[left, mid)中
} else if (nums[mid] < target) {
left = mid + 1;
// target 在右区间，在[mid + 1, right)中
} else { // nums[mid] == target
return mid;
}
}
// 未找到目标值
return -1;
2.2 第一个错误的版本
链接 278. 第一个错误的版本 - 力扣（LeetCode）
分析一下
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while(left < right){
int mid = left + (right - left) / 2;
if(isBadVersion(mid)){
right = mid ;
}else{
left = mid + 1;
}
}
return right;
}
}
2.3 搜索插入位置
链接 35. 搜索插入位置 - 力扣（LeetCode）
分析一下
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = left + (right - left)/2;
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return right+1;
}
}
2.4 在排序数组中查找元素第一个和最后一个位置
链接 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
这个题我们就可以使用二分查找来找它的左右边界
为了便于理解，我们寻找左右边界，分为两个二分查找写左右边界
找左边界
public int getLeftBorder(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
int leftBorder = -2;//用来记录leftBorder没有被赋值的情况
while(left <= right){
int mid = left + (right - left);
if(nums[mid] >= target){
//寻找左边界
right = mid - 1;
leftBorder = right;
}else{
left = mid + 1;
}
}
return leftBorder;
}找右边界
public int getRightBorder(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
int rightBorder = -2;
while(left <= right){
int mid = left + (right - left);
if(nums[mid] > target){
right = mid - 1;
}else{
//寻找右边界
left = mid + 1;
rightBorder = left;
}
}
return rightBorder;
} 分情况讨论了
public int[] searchRange(int[] nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
//数组中没有target，target在数组左边或右边
if(leftBorder == -2 || rightBorder == -2){
return new int[]{-1,-1};
}
//数组中有target，返回这两个target下标
if(rightBorder -leftBorder >1){
return new int[]{leftBorder + 1,rightBorder - 1};
}
//target在数组范围中，但数组不存在target
return new int[]{-1,-1};
}
2.5 x的平方根
链接 69. x 的平方根 - 力扣（LeetCode）
分析一下（因为本篇是只讲解二分查找的，别的方法不提，主要加强二分查找理解）
class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
int ans = -1;
while(left <= right){
int mid = left + (right -left)/2;
if((long)mid*mid <= x){
//这里写乘法的，必须要转成long，不然会溢出
//或者直接写除法，就不考虑溢出了
ans = mid;
left = mid + 1;
}else{
right = mid -1;
}
}
return ans;
}
}
2.6 有效的完全平方数
链接 367. 有效的完全平方数 - 力扣（LeetCode）
简单分析一下
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0;
int right = num;
while(left <= right){
int mid = left + (right - left)/2;
if((long)mid*mid < num){
left = mid + 1;
}else if((long)mid*mid > num){
right = mid - 1;
}else{
return true;
}
}
return false;
}
}
3.总结一下
见到数组的题，我们可以先看一下，有没有顺序，如果有，可以根据题意考虑可以合不合适使用二分查找。
然后再写二分查找时，如何保证你写的二分查找是正确的，可以多想一下这段话
要对区间定义想情楚，区间的定义就是不变量，这里建议可以多画画图.
要在二分查找过程中，保持不变量，就是要用while寻找每一次边界的处理，都要坚持根据区间的定义来操作，这就是循环不变量的规则。
写二分法，区间定义要想清楚，
一般有两种，左闭右闭 [ left , right ] 左闭右开 [ left , right )
相关文章
