Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел 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.

😎 Решение:

class Solution {
    function fixedPoint($arr) {
        $left = 0;
        $right = count($arr) - 1;
        $answer = -1;
        
        while ($left <= $right) {
            $mid = intdiv($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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний