Binary Search

Problem Description

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.

Key Insights

• The problem requires an efficient search method due to the large possible size of the array (up to 10,000 elements).
• A binary search algorithm is appropriate here as it leverages the sorted property of the array to reduce the search space logarithmically.
• The unique elements in the array ensure that we won't encounter duplicates, simplifying the search process.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution employs a binary search algorithm. The approach involves:

1. Initializing two pointers, left and right, to represent the current search bounds.
2. Repeatedly calculating the middle index and comparing the middle element with the target.
3. If the middle element matches the target, its index is returned.
4. If the target is less than the middle element, the search continues in the left half; if greater, in the right half.
5. This process continues until the target is found or the search bounds converge.

Code Solutions