0035. Search Insert Position | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0035.Search-Insert-Position/

[hujun2020]

func searchInsert(nums []int, target int) int {
	start,end,mid := 0,len(nums)-1,0
	for start <= end{
		mid  = start + (end-start)>>1
		if nums[mid] == target{
			return mid
		}else if nums[mid] < target{
			if mid==len(nums)-1 || (nums[mid+1]>target){
				return mid+1
			}
			start = mid + 1
		}else if nums[mid] > target{
			if mid==0 || (nums[mid-1]<target){
				return mid
			}
			end = mid - 1
		}
	}
	return mid
}

[chrisliu12138]

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left <= right{
        mid := left + (right-left)/2   // 防止溢出 等同于(left+right)/2
        if nums[mid] == target{
            return mid
        }else if nums[mid] > target{    //target 在左区间，所以[left, middle - 1]
            right = mid - 1
        }else{
            left = mid + 1              //target 在右区间，所以[middle + 1, right]
        }
    }
	// 分别处理如下四种情况
	// 目标值在数组所有元素之前  [0, -1]
	// 目标值等于数组中某一个元素  return middle
	// 目标值插入数组中的位置 [left, right]，return  right + 1
	// 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
    return right + 1
}