简单好记的二分查找边界算法

市面上已有解法的槽点：

• 边界处理复杂， 一会mid加1，一会不加1； 一会修改right=mid-1，一会right=mid；头疼
• 循环结束后，还要再处理一次边界问题，left是不是越界了，left指向的值是不是target？
• 多种解法，看似高端，实则越记越混乱

本解法的优势：

• 只需知道如何正常的二分查找target，不需要记该不该mid+1，该不该修改right之类的
• 循环结束后，直接返回结果，不需要再次处理边界问题

本解法的思路

• 基于正常的二分查找算法实现，不需要考虑复杂的边界问题
• 在 [left, right] 闭区间内二分查找target
  • 若没有找到target，或者 left>right 搜索区间为空时，停止查找
  • 若找到 target，更新搜索区间为 [新的left, targetPos-1]，并更新左边界索引
    • 然后在 [新的left, targetPos-1] 区间内继续查找 target

代码在这（go实现）

package main

import (
	"fmt"
)

// 正常的二分查找，返回 目标pos、新的left、新的right
func binarySearch(nums []int, left, right, target int) (targetPos, 
 leftPos, rightPos int) {

	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			leftPos, rightPos, targetPos = left, right, mid
			return

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

	targetPos, leftPos, rightPos = -1, -1, -1
	return
}

func leftBound(nums []int, target int) (boundIndex int) {
	boundIndex = -1
	left, right := 0, len(nums)-1

	for left <= right {
		targetPos, leftPos, _ := binarySearch(nums, left, right, target)
		if targetPos == -1 {
			break
		}

		boundIndex = targetPos //每找到一次target，就更新边界索引
		left = leftPos
		right = targetPos - 1 //在target的左边继续查找
	}

	return boundIndex
}

func main() {
	fmt.Println(leftBound([]int{1, 1, 2, 2, 3, 3}, 0)) //-1
	fmt.Println(leftBound([]int{1, 1, 2, 2, 3, 3}, 1)) //0
	fmt.Println(leftBound([]int{1, 1, 2, 2, 3, 3}, 2)) //2
	fmt.Println(leftBound([]int{1, 1, 2, 2, 3, 3}, 3)) //4
	fmt.Println(leftBound([]int{1, 1, 2, 2, 3, 3}, 4)) //-1

	fmt.Println(leftBound([]int{}, 4))                    //-1
	fmt.Println(leftBound([]int{1, 1, 2, 2, 3, 3, 4}, 4)) //6
	fmt.Println(leftBound([]int{1, 1, 2, 3, 3, 4}, 2))    //2

	fmt.Println("Hello World")
}