Условие

Дан отсортированный массив целых чисел и исходное число. Необходимо вернуть индекс элемента, если исходное число есть в массиве или индекс куда необходимо поставить исходное число.

Гарантируется, что дублей в массиве не будет.

Пример 1

Input: [1,3,5,6], 5
Output: 2

Пример 2

Input: [1,3,5,6], 2
Output: 1

Пример 3

Input: [1,3,5,6], 7
Output: 4

Пример 4

Input: [1,3,5,6], 0
Output: 0

Решение

Бинарный поиск

Будем использовать бинарный поиск с некоторыми дополнениями:

• Вернуть 0 если исходное число меньше nums[0]
• Вернуть len(nums) если исходное число больше nums[len(nums)-1]
• Там где обычно в конце алгоримта возвращаем -1 ( элемент не найден ) – вернуть left

func searchInsert(nums []int, target int) int {
    left := 0
    right:=len(nums)-1
    if target>nums[right] {
        return len(nums)
    }
    if target < nums[left] {
        return 0
    }
    for left<=right {
        med := (left+right)/2
        if nums[med] == target {
            return med
        }
        if nums[med]>target {
            right=med-1
            continue
        }
        if nums[med]<target {
            left=med+1
            continue
        }   
    }
    return left
}