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:

Example 2:

Constraints:

• 1 < = n u m s . l e n g t h < = 1 0 4 1 <= nums.length <= 10^4 1<=nums.length<=104
• − 1 0 4 < n u m s [ i ] , t a r g e t < 1 0 4 -10^4 < nums[i], target < 10^4 −104<nums[i],target<104
• 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
}