二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，可以在数据规模的对数时间复杂度内完成查找。

二分查找可以应用于数组，是因为数组具有有随机访问的特点，并且数组是有序的。

二分查找体现的数学思想是「减而治之」，可以通过当前看到的中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。

二分查找问题也是面试中经常考到的问题，虽然它的思想很简单，但写好二分查找算法并不是一件容易的事情。

原理

在升序数组 \(nums\) 中寻找目标值 \(target\)，对于特定下标 \(i\)，比较 \(nums[i]\) 和 \(target\) 的大小：

如果 \(nums[i] = target\)，则下标 \(i\) 即为要寻找的下标；

如果 \(nums[i] > target\)，则 \(target\) 只可能在下标 \(i\) 的左侧；

如果 \(nums[i] < target\)，则 \(target\) 只可能在下标 \(i\) 的右侧。

基于上述事实，可以在有序数组中使用二分查找寻找目标值。

二分查找的做法是，定义查找的范围 \([left,right]\)，初始查找范围是整个数组。每次取查找范围的中点 \(mid\)，比较 \(nums[mid]\) 和 \(target\) 的大小，如果相等则 \(mid\) 即为要寻找的下标，如果不相等则根据 \(nums[mid]\) 和 \(target\) 的大小关系将查找范围缩小一半。

由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 \(O(\log_n)\)，其中 \(n\) 是数组的长度。

二分查找的条件是查找范围不为空，即 \(left \leq right\)。如果 \(target\) 在数组中，二分查找可以保证找到 \(target\)，返回 \(target\) 在数组中的下标。如果 \(target\) 不在数组中，则当 \(left > right\) 时结束查找，返回 \(− 1\)。

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (right-left)/2 + left
        num := nums[mid]
        if num == target {
            return mid
        } else if num > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

例题

278 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 2³¹ - 1

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return            true if current version is bad 
 *                    false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    var low, high, version, result int
    high  = n
    low = 1

    for low <= high {
        version = low + (high - low) / 2

        if isBadVersion(version) {
            high = version - 1
            result = version
        } else {
            low = version + 1
        }
    }

    if isBadVersion(version) {
        return version
    }

    return result
}

35 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums 为 无重复元素 的升序排列数组
-10⁴ <= target <= 10⁴

func searchInsert(nums []int, target int) int {
    var left, right, pos int
    right = len(nums) - 1

    for left <= right {
        pos = left + (right - left) / 2
        if nums[pos] == target {
            return pos
        } else if nums[pos] > target {
            right = pos - 1
        } else {
            left = pos + 1
        }
    }


    if nums[pos] > target{
        return pos
    } else {
        return pos + 1
    }
}

167 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index₁] 和 numbers[index₂] ，则 1 <= index₁ < index₂ <= numbers.length 。

以长度为 2 的整数数组 [index₁, index₂] 的形式返回这两个整数的下标 index₁ 和 index₂。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index₁ = 1, index₂ = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index₁ = 1, index₂ = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index₁ = 1, index₂ = 2 。返回 [1, 2] 。

提示：

2 <= numbers.length <= 3 * 10⁴
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

func twoSum(numbers []int, target int) []int {
    for i := 0; i < len(numbers); i++ {
        low, high := i + 1, len(numbers) - 1
        for low <= high {
            mid := (high - low) / 2 + low
            if numbers[mid] == target - numbers[i] {
                return []int{i + 1, mid + 1}
            } else if numbers[mid] > target - numbers[i] {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
    }
    return []int{-1, -1}
}