算法之旅011 - 二分搜索Level1 Day11

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

题目构成：Medium*2。

1855. Maximum Distance Between a Pair of Values

对于num1中的任意一个位置i和num2中的任意一个位置j，如果i <= j并且nums1[i] <= nums2[j]，则(i, j)是一组有效的数值对，j - i代表此数值对的距离，求所有有效数值对的最大距离。代码(Golang)如下：

    func maxDistance(nums1 []int, nums2 []int) int {
        r := 0
        for i, n1 := range nums1 {
            j, k := i, len(nums2)-1
            if j > k || n1 > nums2[j] {
                continue
            }
            for j <= k {
                p := (j + k) / 2
                v := nums2[p]
                // last num in nums2[j:] larger than or equal to n1
                if v >= n1 {
                    j = p + 1
                } else {
                    k = p - 1
                }
            }
            if k-i > r {
                r = k - i
            }
        }
        return r
    }

遍历nums1中的每一个数n1，然后以这个数为目标在nums2中使用二分搜索，查到最后一个大于等于n1的数，不断更新最大值结果r。

33. Search in Rotated Sorted Array

一个有序数组被翻转了，即数组后未知个元素挪到了前面，查找目标值。代码(Golang)如下：

    func search(nums []int, target int) int {

        i, j := 0, len(nums)-1
        for i <= j {
            m := (i + j) / 2

            p, v, q := nums[i], nums[m], nums[j]

            if v == target {
                return m
            }

            // v和q都在同一个递增的半边序列中
            if v <= q {
                // 如果target也在两者之间
                if v < target && target <= q {
                    i = m + 1
                } else {
                    j = m - 1
                }
            // v和q分属两个半边序列，即p和v在同一个递增的半边序列中
            } else {

                if p <= target && target < v {
                    j = m - 1
                } else {
                    i = m + 1
                }
            }
        }
        return -1
    }

通过判断是否满足p <= target < v或者v < target <= q，来缩小查找范围。