Exercise · Algorithms and Complexity · lesson 7 of 9
Exercise: binary search
Write a function int find_index(const std::vector<int>& sorted, int value). The vector sorted is in ascending order. The function returns the index of the element equal to value, or -1 if there is none. The search must make O(log n) comparisons.
find_index({1, 3, 5, 7, 9}, 7)→3find_index({1, 3, 5, 7, 9}, 4)→-1find_index({}, 5)→-1
Constraints: the values in sorted are distinct int numbers, negative ones included, and the vector may be empty. value may be less than the first element or greater than the last one.
