每日一题---35. 搜索插入位置[力扣][Go]

// 遍历
func searchInsert(nums []int, target int) int {
    index := 0
    for i, num := range nums {
        index = i
        if target <= num {
            break
        }
        index++
    }
    return index
}

// 二分法
func searchInsert(nums []int, target int) int {
    n := len(nums)
    // 定义左右闭区间[l , r]
    l := 0
    r := n-1
    // 因为是闭区间所以 l = r 也有效
    for l <= r {
        // 控制范围
        mid := l + (r - l)/2
        if nums[mid] > target {
            // target 在左区间，所以[l, mid - 1]
            r = mid - 1
        } else if nums[mid] < target {
            // target 在右区间，所以[mid + 1, r]
            l = mid + 1
        } else {
            // 1. 目标值等于数组中某一个元素  return mid;
            return mid
        }
    }
    // 2.目标值在数组所有元素之前 3.目标值插入数组中 4.目标值在数组所有元素之后 return r + 1;
    return r + 1
}