二分查找的几种寻找情况

二分查找的几种寻找情况

查找第一个位置

func findFirst(nums []int, target int) int {
    l, r := 0, len(nums)-1
    ans := -1
    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] == target {
            ans = mid        // 记录位置
            r = mid - 1      // 继续向左搜索
        } else if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}

查找最后一个位置

func findLast(nums []int, target int) int {
    l, r := 0, len(nums)-1
    ans := -1
    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] == target {
            ans = mid        // 记录位置
            l = mid + 1      // 继续向右搜索
        } else if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}

找第一个大于 target 的元素

func findFirstGreater(nums []int, target int) int {
    l, r := 0, len(nums)-1
    ans := -1
    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] > target {
            ans = mid        // 记录候选答案
            r = mid - 1      // 继续向左搜索
        } else {
            l = mid + 1      // 继续向右搜索
        }
    }
    return ans
}

找第一个小于 target 的元素

func findFirstSmaller(nums []int, target int) int {
    l, r := 0, len(nums)-1
    ans := -1
    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] < target {
            ans = mid        // 记录候选答案
            l = mid + 1      // 继续向右搜索
        } else {
            r = mid - 1      // 继续向左搜索
        }
    }
    return ans
}