详解二分查找算法(binary search)
二分查找(binary search)是一种高效的快速查找算法，对于要查找的序列是有序序列。
二分查找虽然是一种简单常用的算法思路，但是我们在用的时候经常会忽视细节。
首先我们看一个最基础的题：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，我们需要在数组中找到这个目标值并返回它的下标，如果没有找到则返回-1。
看到这个题，我们先考虑一下常用的思路，第一种遍历整个数组nums，判断每个元素是否等于target，如果是则返回对应下标，结束返回-1。
第二种可以添加到hash表，值作为key，下标作为value。然后直接取出target值。
第一种时间复杂度O(n)，空间复杂度O(1)。第二种时间复杂度O(1)，但是空间复杂度O(n)。有没有更好的办法？第三种我们就可以考虑二分查找了。
我们首先思考几个问题？
1、我们查找的范围是什么？
2、用哪个值和目标值比较？
3、什么时候查找结束？
以开头的小游戏为例，第一次查找的范围为[0-100]，我们取了中间值50，如果50等于目标值则结束。第二次我们有两个选择，在[0-49]之间选择或者在[51-100]之间选择，，，以此类推，我们需要选取左右的边界left和right以及中间值mid。右边界的确定直接决定了后续的结束条件和区间的选择。
主要分为两种情况：
1）右边界闭区间
如果右边界是闭区间，查找结束就是left>right的时候，也就是left=right+1的时候，再次框选区间的时候右区间也应该是闭区间
2）右边界开区间，查找结束就是left=right的时候，再次选区间的时候右区间也应该是开区间
闭区间例子如下：
python版
class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low = 0high = len(nums)-1 #右区间闭区间，搜索可以到这个边界,搜索范围[left, right]while low<=high:#右区间闭区间，判断条件left会等于rightmid = (high-low)//2+lownum = nums[mid]if num==target:return midelif num>target:high = mid-1#右区间闭区间，搜索范围为[left,mid-1]else:low = mid+1#搜索范围为[mid+1,right]return -1
Java版
class Solution {public int search(int[] nums, int target) {int low = 0;int high = nums.length-1;while (low<=high){int mid = (high-low)/2+low;int num = nums[mid];if (num==target){return mid;}else if (num>target){high = mid-1;}else{low = mid + 1;}}return -1;}}
开区间例子如下：
class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low = 0high = len(nums) #右区间开区间，搜索不到right,搜索范围[left, right)while low<high:#右区间开区间，判断条件left不会等于rightmid = (high-low)//2+lownum = nums[mid]if num==target:return midelif num>target:high = mid#搜索范围在左，搜索范围为[left,mid)else:low = mid+1#搜索范围在右区间，范围为[mid+1,right)return -1
以上是最基础的二分查找的例子，具体的情况需要结合实际的需求灵活更改。
最后总结一下二分查找的基本框架。
int binarySearch(int[] nums, int target) {int left = 0, right = ...;//定义左右b边界while(...) {//判断搜索结束条件int mid = (right + left) / 2;//计算中间值if (nums[mid] == target) {//相等...} else if (nums[mid] < target) {//在右边界的情况left = ...} else if (nums[mid] > target) {//在左边界的情况right = ...}}return ...;}