二分查找以及变种的总结
一、初探二分查找
在面试的时候，尤其的一面，感觉让你手写二分，还真的不一定就能很快写出来，所以在此总结分享给大家
1 二分查找是什么？
”查找“顾名思义是在一堆数去找出我们需要的数，但是我们又想更快的找出我们需要找的数，所以我们就尽量的减少查找比较的次数。"二分"就是分成两份来减少我们查找次数。
不急不急，假设我们这里有十个数，我们来画图看看这是个什么神操作。
从上图我们知道，我们每次都和区间的中间项值进行比较，从而缩小查找区间的值。
2 时间复杂度？
这里我们假设搜索区间一共n个数，第一次切分n/2,第二次n/4,第三次n/8……….n/2(k).这是一个等比数列，n/2^k=1,k=log2n,那么时间复杂度为o(logn).
二 、二分的注意事项
1 二分查找要求数据必须是有序的。
2 二分查找依赖于数组随机查找的特性，要求内存连续
三 、二分的实现
1 第一种小白写法
int BinarySerach(vector<int>& nums,int n, int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = (left+right)/2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid-1;
}
return -1;
}
面试官发话了
2 方法二优化版
如果right和left比较的时候，两者之和可能溢出。那么改进的方法是mid=left+(right-left)/2.还可以 继续优化，我们将除以2这种操作转换为位运算mid=left+((right-left)>>1).
哪有这么简单的事儿，大多数的笔试面试中可能会出现下面的几种情况。
四 、二分的各种变种
这里主要是看看原始数组有重复数的情况。
1 查找第一个值等于给定值的情况(查找元素7)
思路
首先7与中间值a[4]比较，发现小于7，于是在5到9中继续查找，中间a[7]=7,但是这个数7不是第一次出现的。那么我们检查这个值的前面是不是等于7，如果等于7，说明目前这个值不是第一次出现的7，此时更新rihgt=mid-1.ok我们看看代码
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
} else if(nums[mid]<value)
{
left=mid+1;
}else
{
if((mid==0)||(nums[mid-1]!=value))
{
return mid;
}else
{
left=mid-1;
}
}
return -1;
}
2 查找最后一个值等于给定值的情况
假设nums[mid]这个值已经是最后一个元素了，那么它肯定是要找到最后一个值。如果nums[mid]的下一个不等于value，那说明nums[mid]就是我们需要找到最后一个等于给定值的值。
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
} else if(nums[mid]<value)
{
left=mid+1;
}else
{
if((mid==n-1)||(nums[mid+1]!=value))
{
return mid;
}else
{
left=mid+1;
}
}
return -1;
}
3 查找第一个大于等于给定值的情况
1 如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1
2 如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。相反
3 如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>=value)
{
if(mid==0||nums[mid-1]<value)
{
return mid;
}else
{
right=mid-1;
}
}else
{
left=mid+1;
}
return -1;
}
4 查找最后一个小于等于给定值的情况
1 如果nums[mid]小于查找的值，那么需要查找的值肯定在[mid+1,right]之间，所以我们需要更新left=mid+1
2 如果nums[mid]大于等于给定的value，检查nums[mid]是不是我们的第一个值大于等于给定值的元素
int BinarySerach(vector<int>& nums, int n,int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = left+((right-left)>>1);
if (nums[mid]>value)
{
right=mid-1;
}else
{
if(mid==n-1||(nums[mid+1]>value))
{
return mid;
}else
{
left=mid+1;
}
}
return -1;
}