算法题之二分查找

首先针对的数据必须是是：有序数据
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999,9999]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题代码：

class Solution {
    public int search(int[] nums, int target) {
            int low=0,high=nums.length-1;
            while(low<=high){
                int mid=(high-low)/2+low;
                if(nums[mid]==target){
                    return mid;
                }else if(nums[mid]>target){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            return -1;
    }
}

总结：二分查找属于比较简单的算法，但同时非常容易让人犯错，除了必须是有序数据外，还有就是对于边界问题的理解，也就是需不需要等于号的问题。下面口述分析一下思路。
首先，low=0，high=nums.length-1;是基于数组下标的性质设定的。
如果只有一个数据：
low是0，high是0，循环条件必须是<=才能进入循环。
如果是奇数个数据（比如3）：
low=0；high=2；中间的那个数显然是第二个数据，mid=(high-low)/2+low。mid刚好此时为1，刚好对应。接下来就是判断缩小范围（比如指定数据在左半边），那low不变为0，high为1-1=0，两个相等但仍需判断，故循环条件必须是<=。
如果是偶数个数据（比如4）：
low=0；high=3；中间的数据是第二条数据，mid为1。如果指定数据在左半边，那low不变为0，high为1-1=0，两个相等但仍需判断，故循环条件必须是<=。
所以实际操作过程中只要能想到以上的一条，就能判断自己写的代码是对的还是错的。