算法之旅002 - 二分搜索Level1 Day2

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

题目构成：Easy*2。

35. Search Insert Position

二分搜索变形，从有序数组中查找目标值，假设查找的目标不在数组中，把它插入数组应该在哪个位置？代码(Golang)如下：

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

二分到最后，i和j+1就是目标值应该插入的位置，只要把最后return -1改为return i或return j + 1即可。

852. Peak Index in a Mountain Array

数组前一部分升序，后一部分降序，找到最高点，代码(Golang)如下：

    func peakIndexInMountainArray(arr []int) int {
        i, j := 0, len(arr)-1

        for i < j {
            k := (i + j) / 2
            // 如果k到k+1是上升的，说明最高点在k的右边
            if arr[k] < arr[k+1] {
                i = k + 1
            } else {
                j = k
            }

        }
        return i
    }

通过对比中间点与中间点下一个点的大小，可以判断出最高点在当前中间点的左侧还是右侧。此外，还有更快的解法，参考黄金比例分割算法。