算法之旅004 - 二分搜索Level1 Day4

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

题目构成：Easy*2。

69. Sqrt(x)

对一个数开方，返回整数部分，也就是找到一个最大的x使得x*x <= num，还是最基本的二分搜索，代码(Golang)如下：

    func mySqrt(x int) int {
        i, j := 1, x
        for i <= j {
            m := (i + j) / 2
            v := m * m
            if v == x {
                return m
            } else if v > x {
                j = m - 1
            } else {
                i = m + 1
            }
        }
        return j
    }

744. Find Smallest Letter Greater Than Target

找到数组中按字母顺序排在target之后的第一个字母，代码(Golang)如下：

    func nextGreatestLetter(letters []byte, target byte) byte {
        i, j := 0, len(letters)-1

        for i <= j {
            m := (i + j) / 2
            v := letters[m]
            if v > target {
                j = m - 1
            } else {
                i = m + 1
            }
        }
        // if i == len(letters) {
        // 	return letters[0]
        // }
        return letters[i%len(letters)]
    }

注意：
1. 如果v == target，也应该减小边界，执行i = m + 1。
2. 这题还有个坑就是可能没有答案，即数组中所有字母都在target之前，此时应该返回letters中第一个字母。