算法之旅001 - 二分搜索Level1 Day1

跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day1。

题目构成：Easy*2。

704. Binary Search

最基础的二分搜索，从有序数组中查找目标值，代码(Golang)如下：

    func search(nums []int, target int) int {
        i, j := 0, len(nums)-1
        if nums[i] > target || nums[j] < target {
            return -1
        }
        for i <= j {
            k := (i + j) / 2
            v := nums[k]
            // fmt.Println(i, k, j, v)
            if v == target {
                return k
            } else if v > target {
                j = k - 1
            } else {
                i = k + 1
            }
        }
        return -1
    }

需要注意的点有3个：

1. 直接通过有序数组的第一个元素和最后一个元素判断target是否在数组中，以优化效率
   
2. 循环的条件是i<=j，包含等于
   
3. 找到中间位置k之后，缩小区间需要-1或+1，避免计算中值时固定在一个点
   

374. Guess Number Higher or Lower

在指定范围内猜数字，和基础的二分搜索几乎一样，代码(Golang)如下：

    func guess(num int) int

    func guessNumber(n int) int {
        i, j := 1, n
        for i <= j {
            k := (i + j) / 2
            v := guess(k)
            if v == 0 {
                return k
            } else if v == 1 {
                i = k + 1
            } else {
                j = k - 1
            }
        }
        return -1
    }

代码中的guess函数在题目中是内置的，不需要自己提供。