binary search Algorithm

Guide:

1. Binary Search is used to find target integer in a sorted array quickly.
2. Binary search has left, right, and mid variables, but the target variable is what binary search is used for. Assume num2 is a sorted array in which we are searching for target.
3. The Match: If nums2[mid] is exactly equal to your target, you've found a common number! You can immediately return it.
4. Go Right: If your target is greater than nums2[mid], that means your target has to be in the right half of nums2. Move your left pointer to mid + 1.
5. Go Left: If your target is smaller than nums2[mid], your target must be in the left half. Move your right pointer to mid - 1.

//java
int left = 0;
int right = nums2.length - 1;
int mid = 0;
int target = 0;
        
while(left <= right) {
    mid = left + (right - left) / 2;
    if(nums1[i] == nums2[mid]) {
        return target;
    } else {
        if(target < nums2[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
}

Here is the breakdown of the time and space complexity for the Binary Search algorithm:

Time Complexity

Binary search is highly efficient because it halves the search space during every iteration.

• Best Case: O(1)
  This happens when the target element is found precisely at the middle index on the very first check.
• Average Case: O(log n)
  On average, the algorithm consistently divides the remaining array elements by two until the target is found.
• Worst Case: O(log n)
  This occurs when the target element is either at the extreme ends of the array or is not present in the array at all, forcing the algorithm to keep dividing until the search space is completely exhausted.

Space Complexity

The space complexity depends entirely on how you implement the algorithm:

• Iterative Implementation: O(1)
  This is the approach you used in your blog post's code block. It only requires a few integer variables (pointers like left, right, and mid) to track the boundaries. Because these variables take up a constant amount of memory regardless of the size of the array, the auxiliary space is O(1).
• Recursive Implementation: O(log n)
  If you write binary search using a recursive function, the space complexity increases. Each recursive call adds a new frame to the system's call stack. In the worst-case scenario, the maximum depth of the recursion tree will be log n, resulting in an auxiliary space complexity of O(log n).

Example sums to try quickly:

LeetCode: Minimum Common Value