期末考要来了，最近小秋正在从零开始复习算法相关知识…
一道简单的算法题
帅地：听说你最近正在临时饱佛教复习各种算法？
小秋：对啊，算法太难了，把我头都搞大了，不过，感觉自己复习的好像还不错。
帅地：那我找一道简单的题考考你？
小秋：好啊，好啊，正好可以试试水。
帅地：给你一个有序数组，例如
然后我给出一个元素target，你返回它对应数组的下标，如果数组中不存在这个元素的话，则返回-1。例如
1、我给出target=18，则你需要返回5。
2、我给出target=1，你需要返回0。
3、我给出target=10，由于数组中不存在10这个元素，所以你需要返回-1。
小秋：这也太简单了吧，我从左到右遍历数组所有元素，就可以找出来了。
帅地：这是一种方法，不过你这种方法的时间复杂度为O(n)，有没有时间复杂度上更小的方法呢？
小秋：那我可以采用哈希表来存储，把数组元素作为key，对应的下标作为value，这样的话，以后需要查找某个元素了，我就可以在时间复杂度为O(1)找到对应的元素下标了。
帅地：你这种方法，需要用哈希表来存放元素，虽然时间复杂度为O(1)，但是空间复杂度为O(n)了，你能不能在时间复杂度和空间复杂度折中一下，找出更加优美的方法呢？
小秋：好像，，目前没啥思路。
神速的二分查找
帅地：你听说过二分查找吗？
小秋：二分查找？什么鬼？
帅地：这道题就可以用二分查找来解决了，我来给你讲讲吧。
小秋：好啊，好啊。
帅地：其实呢，对于这道题，由于数组是有序的，我们每次在查找的时候，可以直接从中间元素开始比较，例如我们要查找target=10，这个元素，我们把target与数组中间的那个元素15，进行比较。
（1）如果target比15小，那么15以及15右边的所有元素一定比target大，所以target只能存在于15的左边元素中。
（2）如果target比15大，那么15以及15左边的所有元素一定比target小，所以target只能存在于15的右边元素中。
（3）如果target与15相等，则直接把15对应的下标返回即可。
在这个例子中，target=10比15小，所以target只可能存在于15的左边元素中
接下来我们只需要在左半部分查找这个元素就可以了，右半部分的元素可以不用管了，你看，通过这种方式，只需要一次比较，我们就可以把查找的范围缩小了一半。
接着我们继续把target与中间元素比较，这时候中间元素是5，15比5大，所以target只可能存在于5右边的元素中
接下来我们继续查找，这时中间元素是10，和target相等，所以直接把10的下标index=2返回。
二分查找的本质
帅地：小秋啊，这种每次都从中间元素开始比较，并且一次比较后就能把查找范围缩小一半的方法，就叫做二分查找了，这种二分查找的时间复杂度是O(logn)，空间复杂度是O(1)，可以说非常快的了。
小秋：那什么情况下可以使用二分查找这种方法呢？
帅地：要使用二分查找，给的数据需要具备两个基本的特性
（1）给的数据是有序的。
（2）给的数据支持随机访问。
小秋：什么是随机访问呢？
帅地：例如像数组就支持随机访问了，例如你要访问第5个元素，那么你就可以用下标为4，即arr[4]来快速访问第五个元素了。而链表就不支持随机访问了，例如你要访问链表的第5个元素，你无法像数组那样，直接用下标来定位，只能从链表头部一个一个遍历到第五个。
小秋：哦，我知道了，只有支持随机访问，我们才能根据数组最左边和最右边的下标，直接定位到数组的中间元素。
帅地：是的，那你可以根据刚才那道题写一下代码吗？
小秋：没问题。
publicstaticintbinarySearch(inttarget,int[]arr){//数组最左边元素下标intleft=0;//数组最右边元素下标intright=arr.length-1;while(left<=right){//中间元素下标intmid=(right+left)/2;if(arr[mid]>target){right=mid-1;}elseif(arr[mid]<target){left=mid+1;}else{returnarr[mid];}}return-1;}90%的人都会犯的错误
帅地：你写的基本正确，不过有个小问题，就是算中间元素下标那里
mid=(left+right)/2;
你这种方法有时候会产生溢出的哦。例如，我们知道int整数的最大值大概是2^31-1大概为21亿。而left和right这两个数相加是有可能超过21亿的，例如left=12亿，right=13亿。这个时候，两个数的和超过了最大值，就会产生溢出了。
小秋：那该怎么写？
帅地：正确的写法应该是这样的
mid=left+(right-left)/2;
这样，就能保存不会出现溢出的情况了。
文章首发于公众号『苦逼的码农』，更多经常文章欢迎搜索关注，已有150多篇原创，公众号回复『电子书』送你一份精选电子书
二分查找在生活中的骗局
帅地：其实在我们的生活中，二分查找也是有挺多应用的，例如用二分查找来做坏事。
小秋：坏事？可以给我举例看看吗？
帅地：有时候临近一些比赛了，例如全世界性的足球大赛，有时候我们会收到一些邮件，有人谎称他会神预算，例如今天是德国和法国比赛，他会跟你说一定是德国胜，然后跟另外一部分人今天一定是法国胜。
而德国和法国，总有一个人会胜，那么他可以跟10000人说德国胜，10000人说法国胜。我们假如是德国胜了，那么在10000人看来它的预算是正确的。
接着德国和俄罗斯比赛，它会在那10000人中，跟5000人说德国胜，5000人说俄罗斯胜。那么在5000看来它的预算还是正确的…
就这样，每次它都从被他预算正确的那一部分人继续吹他会神预算，那么在有些人看来，他果真连续预算正确，这个时候，这些人可能就会认为，他真的有神预算的能力，于是，可能就会相信它说的话了，进而就会被他所欺骗。
小秋：虽然我没收到这类邮件，但是我经常收到一些六合彩的短信
帅地：是的，这些，就是利用的二分查找的思想了。
文章首发于公众号『苦逼的码农』，更多经常文章欢迎搜索关注，已有150多篇原创，公众号回复『电子书』送你一份精选电子书
二分查找？没有你想的那么简单
帅地：小秋啊，刚才给你讲的那道题，可以说是最简单的了，其实，对于二分查找，有很多变形题的，往往不会那么简单。
小秋：那你可以给我出几道，看我能不能现学现卖。
帅地：那我给你两道题吧。
1、实现pow(x,n)函数：即计算x的n次方。不准使用我之前给你讲的位运算：【算法技巧】位运算装逼指南。
2、搜索选择排序数组：假设按照升序排序的数组在预先未知的某个点上进行了旋转。(例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-1。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是O(logn)级别。
示例1:输入:nums=[4,5,6,7,0,1,2],target=0输出:4示例2:输入:nums=[4,5,6,7,0,1,2],target=3输出:-1
这两道题，可以说是中等难度的变形题了，跟我说说怎么做？
小秋：这…，我才刚学完，能不能给我点时间让让想想？
帅地：大概多长呢？
小秋：不长，两天时间就可以了。
帅地：两天还不长…好吧，那两天后见。
总结
这次主要讲解了二分查找的基本思想以及生活在的例子，二分查找思想虽然不难，不过却有很多不容易的题，后面的问题，如果小秋没做出来，我就下次给大家讲解。如果小秋做出来的，我们就来听听他怎么做的，敬请期待。
看完有收获？那么希望老铁别吝啬你的三连击哦
1、点赞，可以让更多的人看到这篇文章2、关注我的原创微信公众号『苦逼的码农』，第一时间阅读我的文章。公众号后台回复『电子书』，还送你一份电子书大礼包哦。3、也欢迎关注我的博客哦。
作者简介
作者：帅地，一位热爱、认真写作的小伙，目前维护原创公众号：『苦逼的码农』，以写了150多篇文章，专注于写算法、计算机基础知识等提升你内功的文章，期待你的关注。转载说明：务必注明来源（注明：来源于公众号：苦逼的码农，作者：帅地）
