算法介绍
二分查找适用范围不止是有序数组，很多有“二段性”的数组其实都可以使用二分查找，什么是“二段性”呢？在数组中，我们查到某个数不符合条件后，就可以排除它之前或之后的所有数据，这种性质就叫做“二段性”！
我们的二分查找有三种情况：1.朴素的二分模板 2.查找左边界的二分模板 3.查找右边界的二分模板
这几种我们都会讲到！
704.二分查找
一、题目描述
OJ题目链接：力扣（LeetCode）
二、思路解析
三、代码
class Solution {
public:
int search(vector& nums, int target)
{
int left = 0, right = nums.size() - 1;
while(left nums[mid]) left = mid + 1;
else right = mid - 1;
}
return -1;
}
};
34.在排序数组中查找元素的第一个和最后一个位置
一、题目描述
非递减顺序：两个相邻的数后面的大或者两数相等
时间复杂度O(logn)联想到二分查找！
二、思路解析
三、代码
class Solution {
public:
vector searchRange(vector& nums, int target)
{
if(!nums.size()) return {-1, -1};//处理边界情况
int left = 0, right = nums.size() - 1;
int begin = -1, end = -1;
while (left = target) right = mid;
else left = mid + 1;
}
//判断是否满足题意
if(nums[left] == target) begin = left;
left = 0, right = nums.size() - 1;
while(left target) right = mid - 1;
else left = mid;
}
if(nums[right] == target) end = right;
return {begin, end};
}
};
35.搜索插入位置
一、题目描述
OJ题目链接：力扣（LeetCode）
二、思路解析
三、代码
class Solution {
public:
int searchInsert(vector& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left = target) return left;
return left + 1;
}
};
69.x的平方根
一、题目描述
OJ题目链接：力扣（LeetCode）
二、思路解析
三、代码
class Solution {
public:
int mySqrt(int x)
{
if (x 
