二分查找

问题

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

代码

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

解释

假设有一数组[1,2,3,4,5,6,7,8,9,10,11,12]，现在我要找到5。

while循环第一次：

start = 0、end =11、mid=5，根据mid找到nus[mid]在数组中对应的是6；

[1,2,3,4,5,6,7,8,9,10,11,12]

发现这次找到的为6，比想要找的5还要大，设置结束end为mid-1，start不变，将查找范围缩小到[1,2,3,4,5]；

目前的查到的数组从[1,2,3,4,5,6,7,8,9,10,11,12]到[1,2,3,4,5,6,7,8,9,10,11,12]；

while循环第二次：

start=0、end=4、mid=2，根据mid找到nus[mid]在数组中对应的是3；

[1,2,3,4,5,6,7,8,9,10,11,12]

这次发现找到的为3，比目标5小，此时将其实start设定为mid+1，end不变，将查到范围缩小到[4,5]；

目前的查找的数组从[1,2,3,4,5,6,7,8,9,10,11,12]到[1,2,3,4,5,6,7,8,9,10,11,12]；

while循环第三次：

start=3、end=4、mid=3，根据mid找到nus[mid]在数组中对应的是4；

[1,2,3,4,5,6,7,8,9,10,11,12]

这次发现找到的4，比目标5小，此时将其实start设定为mid+1，end不变，将查到范围缩小到[5]；

目前的查找的数组从[1,2,3,4,5,6,7,8,9,10,11,12]到[1,2,3,4,5,6,7,8,9,10,11,12]；

while循环第四次：

start=4、end=4、mid=4，根据mid找到nus[mid]在数组中对应的是5；

符合目标，结束返回mid，为4；

[1,2,3,4,5,6,7,8,9,10,11,12]；

至此，找到目标数字的位置，为4；

使用此算法的条件

必须是对一个有序数组或list进行查找可以使用，如果是乱序，此算法返回为-1；

若查询的数组或list是乱序，考虑使用别的算法；