Problem statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints

• 1 <= nums.length <= 10^4.
• -10^4 < nums[i], target < 10^4.
• All the integers in nums are unique.
• nums is sorted in ascending order.

Solution: Divide and Conquer

Since nums is sorted in ascending order you can divide it into subparts to find the target. You can use the middle elements of nums to divide the subparts. target might equal to that element, on the left subpart or in the right subpart.

Code

#include <vector>
#include <iostream>
using namespace std;
int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}
int main() {
    vector<int> nums{-1,0,3,5,9,12};
    cout << search(nums, 9) << endl;
    cout << search(nums, 2) << endl;
}

Output:
4
-1

Complexity

• Runtime: O(logN) where N = nums.length.
• Extra space: O(1).

Implementation notes

• mid is actually (right + left) / 2. But (right + left) might be too big to be overflow before the division. To avoid that overflow you can rewrite the expression to mid = left + (right - left) / 2.