Задача: 33. Search in Rotated Sorted Array
Сложность: medium

Дан массив nums, отсортированный по возрастанию и повернутый на некотором неизвестном индексе. Необходимо найти индекс элемента target. Если он не найден — вернуть -1. Решение должно работать за O(log n).

Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

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

1⃣Инициализируем границы бинарного поиска: left = 0, right = n-1.

2⃣В цикле проверяем значение в середине. Если совпадает с target — возвращаем индекс.

3⃣Определяем, какая половина массива отсортирована, и сужаем поиск к той части, где может находиться target.

😎 Решение:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            if (nums[m] == target) {
                return m;
            }
            if (nums[left] <= nums[m]) { // левая часть отсортирована
                if (nums[left] <= target && target < nums[m]) {
                    right = m - 1;
                } else {
                    left = m + 1;
                }
            } else { // правая часть отсортирована
                if (nums[m] < target && target <= nums[right]) {
                    left = m + 1;
                } else {
                    right = m - 1;
                }
            }
        }
        return -1;
    }
};

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