基本介绍二分查找（halfsearch）是一种查找有序数组中特定元素的查找算法。从定义可以看出，使用二分查找的前提是数组必须是有序的。另外，输入不一定是数组，也可能是给定区间的起止位置。他的时间复杂度是O(lgn)，效率很高。基本特征及其缺点要求对要搜索的数组或范围进行排序。如果对数组进行动态删除和插入操作并完成查找，平均复杂度将变为O(n)。因此，当输入的数组或区间是有序的且不经常变化，需要找到满足条件的元素时，二分查找是最好的选择。解题思路二分查找广义的解题思路是：从排序好的数组或范围中取出位于中间位置的元素，判断该元素是否满足要查找的条件。如果是，则停止搜索并结束程序。如果中间的元素不满足条件，则从它两边的区域开始查找。由于数组是有序的，我们可以使用排除的方法来确定接下来应该搜索这两个区间中的哪一个。通过判断，如果在左半区间找到了真正要找的元素，则继续在左半区间进行二分查找。反之，在区间的右半部分进行二分查找。二分查找问题求解框架intbinarySearch(int[]nums,inttarget){intleft=0,right=...;while(...){//计算mid时，需要技巧防止溢出，建议写成：mid=left+(right-left)/2intmid=(right+left)/2;如果(nums[mid]==target){...}elseif(nums[mid]target){right=...}}return...;}常见解法递归解法假设我们想从一个有序数组中得到{1,3,4,6,7,8,10,13,14}检查数字7是否在里面，如果是，返回它的下标，否则返回-1。递归写法的代码模板如下：//在二分查找函数的定义中，除了指定数组nums和目标查找数target外，还需要指定数组的起始位置和结束位置搜索区间，分别用low和high表示。intbinarySearch(int[]nums,inttarget,intlow,inthigh){//为了避免死循环，先判断，如果开始位置大于结束位置，说明这是非法范围，并且所有的搜索范围都试过了还是没有找到结果，返回-1。如果（低>高）{返回-1;}//取中间数的下标中间。intmiddle=low+(high-low)/2;//检查中间的数字是否是你要找的目标数字，如果是，则返回中间的下标。if(nums[middle]==target){returnmiddle;}//如果发现目标数在左边，则从左半边开始递归进行二分查找。if(targethigh){return-1;}intmiddle=low+(high-low)/2;//判断是否为下边界时，先检查中间的数是否为目标，判断该数是否已经是数组的第一个数，或者它左边的数是否已经小于它，如果两者都满足，则为下边界。if(nums[middle]==target&&(middle==0||nums[middle-1]high){return-1;}intmiddle=low+(high-low)/2;//判断是否为上边界时，先检查中间的数是否为目标，判断该数是否为数组中的最后一个数，或者其右边的数是否大于它，如果都满足了，那就是上界。if(nums[middle]==target&&(middle==nums.length-1||nums[middle+1]>target)){returnmiddle;}if(targethigh){returnnull;}intmiddle=low+(high-low)/2;//判断中点在哪里当数是第一个大于target的数时，必须同时满足两个条件：数middle必须大于target；middle是第一个数字，或者是小于或等于target之前的数字。if(nums[middle]>target&&(middle==0||nums[middle-1]<=target)){returnmiddle;}if(targetnums[mid]。在这个例子中，6>2。在这种情况下，后半部分是有序的。因此，如果nums[mid]代码实现了intbinarySearch(int[]nums,inttarget,intlow,inthigh){if(low>high){return-1;}//判断是否超出搜索范围，超出则返回-1。intmiddle=low+(high-low)/2;//取中位数。if(nums[middle]==target){returnmiddle;}//判断中位数是否是你要找的数if(nums[low]<=target&&targethigh){返回-1;}intmiddle=low+(high-low)/2;if(logs[middle]==null&&logs[middle-1]!=null){returnmiddle;}if(logs[middle]==null){returnbinarySearch(logs,low,middle-1);}else{returnbinarySearch(logs,middle+1,high);}}`
