二分查找

LC 704. Binary Search 二分查找

https://leetcode.com/problems/binary-search/

给定一个【有序】【不重复】数组和一个目标值，找到这个元素的索引；如果不存在，返回 -1

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

一般算法中使用的都是 [left, right) 区间

如果想要 [left, right] 区间的话

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

二分查找【寻找左侧边界】

给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1

func searchLeft(nums []int, target int) int {
    left, right := 0, len(nums)
    
    for left < right {
        mid := left + (right - left) / 2
        
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    // 此时 left=right
    // 算法核心思想为【持续收缩右边界至 >= target 的最小索引】
    // -> 如果 target < min(nums) 返回 0
    // -> 如果 target > max(nums) 返回 len(nums)
    
    if right >= len(nums) || nums[right] != target {
        // NOTE: 此时 right 是【大于 target 的最小索引】
        // 例如：[1, 3, 5, 7] target=4
        // 返回的是 2 <- 指向了 5
        
        return -1
    }
    
    return right
}

可利用牛客进行测试：https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9

class BinarySearch {
public:
    int getPos(vector<int> nums, int n, int target) {
        int left = 0, right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        if (right >= n || nums[right] != target) {
            return -1;
        }

        return right;
    }
};

二分查找【寻找右侧边界】

给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1

方法一

func searchRight(nums []int, target int) int {
    left, right := 0, len(nums)
    
    for left < right {
        mid := left + (right - left) / 2
        
        if nums[mid] <= target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid
        }
    }
    
    // 算法核心思想为【持续收缩左边界至 <= target 的最大索引 + 1】
    
    if left <= 0 {
        return -1
    }
    
    return left - 1
}

整体思路刚好与 searchLeft 相反，为收缩左边届 ——

方法二：利用 leftBound

上一题的 searchLeft 中其实隐含了一个「找到 >= target 的最小索引」的方案（称为 leftBound）

利用 leftBound 可知，找到「== x 的最右侧索引」问题可以转换为找到「>= x+1 的最左侧索引再 -1」即 leftBound(target+1)-1

func searchRight(nums []int, target int) int {
    // 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1
    x := leftBound(nums, target + 1) - 1
    
    // 注意此时 target+1 过小时，x = -1
    if x == -1 || nums[x] != target {
        return -1
    }
    
    return x
}

// 返回  >= target 的最小索引
func leftBound(nums []int, target int) int {
    left, right := 0, len(nums)
    
    for left < right {
        mid := left + (right - left) / 2
        
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return right
}

// 上面的 leftBound 是从之前的 searchLeft 中拆出来的 —— 利用 leftBound 重写 searchLeft 的话如下
func searchLeft(nums []int, target int) int {
    x := leftBound(nums, target)
    
    if x >= len(nums) || nums[x] != target {
        return -1
    }
    
    return x
}

LC.34 Find. First and Last Position of Element in Sorted Array 在排序数组中找元素的第一个和最后一个位置【寻找左右边界】

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

利用 leftBound 完成：

func searchRange(nums []int, target int) []int {
    l := searchLeft(nums, target)
    if l == -1 {
        return []int{-1, -1}
    }
    r := searchRight(nums, target)
    
    return []int{l, r}
}

func searchLeft(nums []int, target int) int {
    x := leftBound(nums, target)
    
    if x >= len(nums) || nums[x] != target {
        return -1
    }
    
    return x
}

func searchRight(nums []int, target int) int {
    // 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1
    x := leftBound(nums, target + 1) - 1
    
    // 注意此时 target+1 过小时，x = -1
    if x == -1 || nums[x] != target {
        return -1
    }
    
    return x
}

// 返回  >= target 的最小索引
func leftBound(nums []int, target int) int {
    left, right := 0, len(nums)
    
    for left < right {
        mid := left + (right - left) / 2
        
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return right
}

LCCN LCR 172. 统计目标成绩的出现次数

https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/

本题与上一题几乎一样（只有返回值不一样）

采用 rightBound 完成：

func countTarget(scores []int, target int) int {
    l := searchLeft(scores, target)
    if l == -1 {
        // score not exist
        return 0
    }
    r := searchRight(scores, target)
    return r-l+1
}

func searchLeft(nums []int, target int) int {
    x := rightBound(nums, target-1) + 1
    if x >= len(nums) || nums[x] != target {
        return -1
    }
    return x
}

func searchRight(nums []int, target int) int {
    x := rightBound(nums, target)
    if x < 0 || nums[x] != target {
        return -1
    }
    return x
}

// 返回 <= target 的最大索引
func rightBound(nums []int, target int) int {
    left, right := 0, len(nums)

    for left < right {
        mid := left + (right - left) / 2

        if nums[mid] <= target {
            left = mid + 1
        } else{
            right = mid
        }
    }

    return left - 1
}

LC.278 First Bad Version 第一个错误的版本