Nhut Nguyen
Nhut Nguyen

Follow

Nhut Nguyen

Follow
Basic Divide and Conquer with Binary Search

Basic Divide and Conquer with Binary Search

Nhut Nguyen's photo
Nhut Nguyen
·Mar 26, 2022·

2 min read

Play this article

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.

Did you find this article valuable?

Support Nhut Nguyen by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this