LeetCode //C - 704. Binary Search

704. Binary Search

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.

From: LeetCode
Link: 704. Binary Search

Solution:

Ideas:

1. Initialize Pointers: It starts by initializing two pointers, left and right, which represent the indices of the start and end of the segment of the array currently being considered. Initially, left is 0 (the first index of the array) and right is numsSize - 1 (the last index of the array).

2. Loop Until Found or Exhausted: The search continues as long as left is less than or equal to right, meaning there is still a portion of the array left to be examined.

3. Calculate Midpoint: Inside the loop, it calculates the midpoint mid of the current segment as left + (right - left) / 2. This avoids potential overflow that could occur if left and right are large integers.

4. Check Midpoint Value:

• If the value at mid is equal to the target, the search is successful, and the index mid is returned.
• If the value at mid is less than the target, the target can only be in the right segment of the current midpoint. Therefore, the left pointer is moved to mid + 1.
• If the value at mid is greater than the target, the target can only be in the left segment of the current midpoint. Therefore, the right pointer is moved to mid - 1.

5. Target Not Found: If the loop ends without finding the target (meaning left becomes greater than right), the function returns -1, indicating that the target is not present in the array.

Code:

int search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoid potential overflow
        if (nums[mid] == target) {
            return mid; // Target found
        } else if (nums[mid] < target) {
            left = mid + 1; // Focus on the right half
        } else {
            right = mid - 1; // Focus on the left half
        }
    }
    return -1; // Target not found
}