Сложность: medium
Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.
Пример:
Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.
👨💻 Алгоритм:
1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.
2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.
3⃣Верните answer.
😎 Решение:
func fixedPoint(arr []int) int {
left, right := 0, len(arr) - 1
answer := -1
for left <= right {
mid := (left + right) / 2
if arr[mid] == mid {
answer = mid
right = mid - 1
} else if arr[mid] < mid {
left = mid + 1
} else {
right = mid - 1
}
}
return answer
}Ставь 👍 и забирай 📚 Базу знаний