手撕二分查找及其变种，就是干!

我是程序员小贱

关注

发布于: 2020 年 08 月 14 日

一、初探二分查找

>在面试的时候，尤其的一面，感觉让你手写二分，还真的不一定就能很快写出来，所以在此总结分享给大家

1 二分查找是什么？

”查找“顾名思义是在一堆数去找出我们需要的数，但是我们又想更快的找出我们需要找的数，所以我们就尽量的减少查找比较的次数。"二分"就是分成两份来减少我们查找次数。

不急不急，假设我们这里有十个数，我们来画图看看这是个什么神操作。

从上图我们知道，我们每次都和区间的中间项值进行比较，从而缩小查找区间的值。

2 时间复杂度？

这里我们假设搜索区间一共 n 个数，第一次切分 n/2,第二次 n/4,第三次 n/8..........n/2(k).这是一个等比数列，n/2(k)=1,k=log2n,那么时间复杂度为 logn.

二、二分的注意事项

1 二分查找要求数据必须是有序的。

2 二分查找依赖于数组随机查找的特性，要求内存连续

三、二分的实现

1 第一种小白写法

int BinarySerach(vector<int>& nums, int target) {    int left = 0, right = nums.size();    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;    }    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;}

复制代码

六结尾

好了，今天文章就到这了，如果你读到这里了，老铁么么哒！非常感谢！

点关注，不跑路

文章会首于与微信，可以微信搜索[我是程序员小贱]第一时间查看。

后面每周都会更新几篇面试高频题目和自己总结的文章，如果觉得学到了一点东西，来个三连击，点赞，关注，分享。

创作不易，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！

如果本篇博客有任何错误，请批评指教，不胜感激！

发布于: 2020 年 08 月 14 日阅读数: 67

原文链接:【http://xie.infoq.cn/article/60d623f088fcf8b1aede5ae71】。文章转载请联系作者。

我是程序员小贱

关注

公众号【我是程序员小贱】干货分享 2019.10.15 加入

计算机小硕，热爱分享

发布

暂无评论

创作场景

手撕二分查找及其变种，就是干!

一、初探二分查找

1 二分查找是什么？

2 时间复杂度？

二 、二分的注意事项

三 、二分的实现

四 、二分的各种变种

六 结尾

我是程序员小贱

评论

二、二分的注意事项

三、二分的实现

四、二分的各种变种

六结尾