算法017：二分查找
二分查找. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/binary-search/
二分查找，其实是双指针的一种特殊情况，但是时间复杂度极低，仅为𝑂(log𝑛)，但是二分查找对于数组的要求必须是有序数组才可以。
我们定义一个左指针和右指针，同时把mid设置程left和right的中间值
- 先让mid处的数字和target相比较
- 如果是 mid > target，说明需要找的值比mid要小，区间在left到mid之间，此时把right指针换到mid的左边，这样就能完成对一般的筛选。
- mid < target则是一样的，只不过翻了过来，把left指针换到mid的右边
当mid处的值和target相等的时候，返回mid处的值。
最终当left > right时，停止循环。如停止循环，则说明没有想要找的值。
另外有一个小细节：
在确定mid的值的时候，为了防止数字太大溢出，不能直接用left + right再除以二这样的方式，而最好用 left + (right - left) / 2 这样的方式，只要右指针不超过最大值，那么mid的值就是有效的。
代码：
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}else{return mid;}}return -1;}
}