Blind 75 - problem 11 : Binary Search

Problem Statement:

Binary Search

The Binary Search algorithm is used to find the position of a target value within a sorted array. Given a sorted array of integers nums and a target value target, the goal is to return the index of the target. If the target is not found, return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists at index 4.

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in the array.

---

Optimal Approach:

Binary search is the most efficient way to find an element in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the target is less than the value in the middle of the interval, the search continues in the lower half, otherwise in the upper half.

• Time Complexity: O(log n), because we divide the search space in half at each step.
• Space Complexity: O(1), as no extra space is needed beyond the input array.

---

LeetCode-Compatible Code Implementations:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
};

---

Step-by-Step Explanation of Code:

1. Initialize Pointers: We initialize two pointers, left and right, at the start and end of the array.

2. Loop until left <= right: The loop continues until we exhaust the search space or find the target.

3. Calculate mid: At each iteration, calculate the middle index as mid = left + (right - left) / 2.

4. Check for Target: If the value at nums[mid] is equal to target, return mid.

5. Update Search Range: If nums[mid] is less than target, move left to mid + 1. If nums[mid] is greater than target, move right to mid - 1.

6. Return -1 if not found: If the loop finishes without finding the target, return -1.

---

Dry Run / Execution Steps:

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

1. left = 0, right = 5, mid = 2 → nums[mid] = 3 (not 9), so move left = mid + 1 → left = 3
2. left = 3, right = 5, mid = 4 → nums[mid] = 9 (found target), return 4

Output: 4

---

Alternative Approaches & Why Not?

1. Brute Force: Iterate through the array to find the target.

   • Time Complexity: O(n)
   • Space Complexity: O(1)
   • Reason for being less optimal: Binary Search is more efficient, with O(log n) time complexity.

2. Sorting: Sorting the array and then applying Binary Search.

   • Time Complexity: O(n log n) (due to sorting)
   • Space Complexity: O(log n)
   • Reason for being less optimal: Sorting before performing Binary Search introduces unnecessary overhead.

---

Best Solution & Why It’s Best:

The Binary Search algorithm is the most efficient solution for this problem. It ensures that you can find the target in logarithmic time. Using brute force or sorting would be less efficient due to higher time complexity.

Comparison:

Approach	Time Complexity	Space Complexity
Binary Search	O(log n)	O(1)
Brute Force	O(n)	O(1)
Sorting + BS	O(n log n)	O(log n)

---

Complexity Analysis:

• Binary Search (Optimal):

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

• Brute Force:

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

• Sorting + Binary Search:

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

---

Conclusion:

The Binary Search approach is the most efficient way to solve this problem. It's fast, with a time complexity of O(log n), and uses minimal space. If you're looking to practice similar problems, here are a few suggestions:

• Find Peak Element
• Search Insert Position
• Find Minimum in Rotated Sorted Array