LeetCode 704. Binary Search

LeetCode 704. Binary Search

LINK: https://leetcode.com/problems/binary-search/

Matter

You are given a sorted integer array in ascending order and a target value.

Your task is to efficiently determine whether the target exists in the array.
If found, return its index. Otherwise, return -1.

The solution must run in logarithmic time.

Example.

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

Output:
4

Explanation:
The value 9 is located at index 4.

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

Output:
-1

Explanation:
The value 2 does not exist in the array.

Constraints

1 <= nums.length <= $10^4$

-$10^4$ < nums[i], target < $10^4$

All values are unique

The array is sorted in ascending order

Problem analysis

Since the array is already sorted, we can eliminate half of the search space at each step.

Instead of scanning linearly, we repeatedly compare the middle element with the target.

• If the middle value is equal → return index
• If the target is smaller → search left half
• If the target is larger → search right half

This reduces the time complexity to $O(\log n)$.

Solution

class Solution 
{
public:
    int search(std::vector<int>& nums, int target) 
    {
        int i32Result = -1;
        int i32IndexL = 0;
        int i32IndexH = (int)nums.size() - 1;

        while(true)
        {
            int i32Index = (i32IndexL + i32IndexH) / 2;
            int i32Value = nums[i32Index];

            if(target == i32Value)
            {
                i32Result = i32Index; 
                break;
            }
        
            if(target > nums[i32Index])
                i32IndexL = i32Index + 1; 
            else
                i32IndexH = i32Index - 1; 

            if(i32IndexL > i32IndexH)
                break;
        }   

        return i32Result;
    }
};