力扣数组基础之二分法

发表于

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

示例

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

思路

二分法区间一般有两种：左闭右闭[left, right]和左闭右开[left, right)，这里以左闭右闭为例：

定义target在左闭右闭区间[left, right]内：

  • 循环要使用left<=right的边界条件，因为left==right是有意义的；
  • 当nums[mid]>target时，此时nums[mid]一定不是target，故把right更新成mid-1;

示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func search(nums []int, target int) {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left) / 2
        if nums[mid] > target {
            right = mid - 1
        }else if nums[mid] < target {
            left = mid + 1
        }else {
            return mid 
        }
    }
    return -1
}