Binary Search easy

Problem Statement

Given a sorted (in ascending order) integer array nums of n integers and a target integer, 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

Steps & Explanation

The problem requires us to implement a binary search algorithm. Binary search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the lower half; otherwise, it continues in the upper half. This process is repeated until the target value is found or the search interval is empty.

Here's a breakdown of the steps:

1. Initialization: Set left pointer to 0 (start of the array) and right pointer to nums.size() - 1 (end of the array).

2. Iteration: While left is less than or equal to right:

   • Calculate the mid index: mid = left + (right - left) / 2. This prevents potential integer overflow issues.
   • Compare nums[mid] with target:
     • If nums[mid] == target, return mid (target found).
     • If nums[mid] < target, the target must be in the right half, so update left = mid + 1.
     • If nums[mid] > target, the target must be in the left half, so update right = mid - 1.

3. Target not found: If the loop completes without finding the target, return -1.

Code (C++)

class Solution {
public:
    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) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; 
    }
};

Complexity Analysis

• Time Complexity: O(log n) - Binary search halves the search space with each iteration.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size. This is because we only use a few variables (left, right, mid) to track the indices.