算法宝典——二分查找算法
1.认识二分查找
二分查找的时间复杂度:O(logN)
二分查找属于算法中耳熟能详的一类，通常的我们会说只有数组有序才可以使用二分查找，不过这种说法并不完全正确，只要数据具有"二段性"就可以使用二分查找，即我们可以找出一种规律将数据分为两部分，然后以此类推处理整个数据即可
二分查找有三种模版：1.朴素二分查找 2.查找左边界的二分查找 3.查找右边界的二分查找
我们这里首先介绍最简单的朴素二分查找，通常朴素二分查找的模版如下
int left = 0,right = nums.size() - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;//防止数据溢出
if(......)
{
right = mid - 1;
}
else if(......)
{
left = mid + 1;
}
else
{
return ......;
}
}
2.实战练习
题目来源：704.二分查找——力扣
这里的数组默认有序，所以这里的"二段性"是将数组分为比target大和比target小两个区间，然后逐区间处理即可
class Solution {
public:
int search(vector<int>& nums, int target)
{
int left = 0,right = nums.size() - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;//防止数据溢出
if(target < nums[mid])
{
right = mid - 1;
}
else if(target > nums[mid])
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
};