704. Бинарный поиск (Binary Search)

Задание.

Даны массив целых чисел nums, который отсортирован в порядке возрастания, и целочисленное target.

Напишите функцию для поиска target в nums. Если target существует, то верните индекс. В противном случае верните значение -1.

Нужно написать алгоритм со сложностью во время выполнения O(log n).

Пример 1.

Входные данные: nums = [-1,0,3,5,9,12], target = 9

Результат: 4

Пояснение: 9 есть в nums и его индекс 4

Пример 2.

Входные данные: nums = [-1,0,3,5,9,12], target = 2

Результат: -1

Пояснение: 2 нет в nums, поэтому возвращается -1

Решение.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;
        int mid;
        
        while(start <= end) {
            mid = (start + end) / 2;
            if(target == nums[mid]) {
                return mid;
            } else if(target < nums[mid]) {
                end = mid-1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
};

Способ решения.