704. Binary Search

Prompt

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.

Constraints:

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

Examples

• 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

Solutions

Solution

In C++

int search(vector<int>& nums, int target) {
	int l = 0; int r = nums.size() - 1;
	while (l <= r) {
		int m = (r - l) / 2 + l;
		int curr = nums[m];
		if (target > curr) l = m + 1;
		else if (target < curr) r = m - 1;
		else return m;
	}
	return -1;
}

Explanation

The quintessential binary search algorithm; sorted containers have $O(\log n)$ search time.

Big O Analysis

Time Complexity

$O(\log n)$

Auxiliary Space Complexity

$O(1)$