algoadvance

Leetcode 704. Binary Search

Problem Statement

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

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

Clarifying Questions

1. Input Range:
   • What is the range of the integer values in nums?
   • How large can the array nums be?
2. Duplicates:
   • Are there duplicate elements in the array, or is it guaranteed that all elements are unique?

Example

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Constraints

• You must implement a binary search algorithm with O(log n) runtime complexity.
• The input array nums is sorted in ascending order.
• The size of the array nums can be up to (10^4) elements.
• The values in nums can range between (-10^4) to (10^4).

Strategy

To solve this problem using binary search, follow these steps:

1. Initialize two pointers: left at the beginning of the array and right at the end of the array.
2. While left is less than or equal to right, do the following:
   • Calculate the middle mid index.
   • Compare the mid-value to the target value.
   • If the mid-value equals the target, return the mid index.
   • If the mid-value is less than the target, move the left pointer to mid + 1.
   • If the mid-value is greater than the target, move the right pointer to mid - 1.
3. If the target is not found, return -1.

Code

#include <vector>

class Solution {
public:
    int search(std::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;
    }
};

Time Complexity

• Time Complexity: O(log n), where n is the number of elements in nums. The binary search algorithm divides the search interval in half with each iteration.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

This solution efficiently searches the sorted array for the target value using the binary search algorithm and meets the required O(log n) runtime complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?