Задача: 35. Search Insert Position
Сложность: easy

Дан отсортированный массив различных целых чисел nums и число target. Необходимо вернуть индекс target, если он найден. Если target отсутствует, вернуть индекс, куда он должен быть вставлен, чтобы сохранить порядок.
Алгоритм должен работать за O(log n).

Пример:

  
Input: nums = [1,3,5,6], target = 5  
Output: 2  

👨‍💻 Алгоритм:

1⃣Используем бинарный поиск для нахождения target или позиции, куда его можно вставить.

2⃣сли nums[mid] == target, возвращаем mid.

3⃣Если nums[mid] < target, продолжаем поиск справа, иначе — слева.

😎 Решение:

class Solution {
    function searchInsert($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);
            if ($nums[$mid] == $target) {
                return $mid;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $left;
    }
}

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