二分查找

描述

leetcode 官方第 704 题，给定一个 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

提示：

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

思路

本题的前提思路是给出的数组已经是有序的数组。我们可以使用二分法进行慢慢的排除来找到对应的值是否在数组里面。

二分法的主要思想是取数组的中间数据作为比较对象，如果给定的数值与中间的关键字相等，那么就返回其数组下标，如果中间的关键字比给定的值大，那么就需要在中间记录的左半边的区域进行查找。如果中间的关键字比给定的值小，那么就需要在中间记录的右半边区域进行查找。不断的重复上述过程。

我们以示例1为例子，原始数组如下：

当我们首次进行坐标赋值的时候如下：

low 表示的是一个数据区间里面的左边的数据，也就是小数据的坐标。high 表示的是一个数据区间里面的右边的数据，就是大的数据的坐标。mid 是取大数据和小数据之间的数据。用 mid 的数据来和需要比较的数值进行比较。我们看到 mid 对应的数值是 3 < 9，所以我们需要将 low 移动到 mid 的右边一个位置，mid 的位置是 (3 + 5) / 2 = 4。如下：

我们可以看到当前的步骤中，mid 对应的数值是 9，和题目中需要比对的数值相等，所以我们将 mid 返回，就找到了数组中的位置。

代码具体实现

Java语言代码实现

class Solution {
    public int search(int[] nums, int target) {  
        //最小值的坐标
        int low = 0;
        //数组中最大值坐标
        int high = nums.length - 1;
        //最小值和最大值坐标的中间坐标
        int mid = 0;
        while(low <= high){
            //两个数据的中间值
             mid = (high + low) / 2;
             if(nums[mid] > target){
                 high = mid - 1;
             }else if(nums[mid] < target){
                 low = mid + 1;
             }else {
                 return mid;
             }
        }
        return -1;
    }
}

Go语言具体实现

func search(nums []int, target int) int {
        //最小值的坐标
         low := 0
        //数组中最大值坐标
        high := len(nums) - 1
        //最小值和最大值坐标的中间坐标
        mid := 0
        for low <= high{
            //两个数据的中间值
            mid = (high + low) / 2
            if nums[mid] > target {
                high = mid - 1
            }else if nums[mid] < target {
                low = mid + 1
            }else {
                return mid
            }
        }
        return -1;
}