Условие
Дан отсортированный массив целых чисел и исходное число. Необходимо вернуть индекс элемента, если исходное число есть в массиве или индекс куда необходимо поставить исходное число.
Гарантируется, что дублей в массиве не будет.
Пример 1
1
2
|
Input: [1,3,5,6], 5
Output: 2
|
Пример 2
1
2
|
Input: [1,3,5,6], 2
Output: 1
|
Пример 3
1
2
|
Input: [1,3,5,6], 7
Output: 4
|
Пример 4
1
2
|
Input: [1,3,5,6], 0
Output: 0
|
Решение
Бинарный поиск
Будем использовать бинарный поиск с некоторыми дополнениями:
- Вернуть
0 если исходное число меньше nums[0]
- Вернуть
len(nums) если исходное число больше nums[len(nums)-1]
- Там где обычно в конце алгоримта возвращаем
-1 ( элемент не найден ) – вернуть left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
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
}
|