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