Binary Search

Problem

Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty.

Examples:

Example 1:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 7
Output: 6 (index of target value)
Explanation: The algorithm finds the target value 7 at index 6.

Example 2:
Input: arr = [1, 3, 5, 7, 9], target = 4
Output: -1 (target not found)
Explanation: The target value 4 is not in the array, so the algorithm returns -1.

Solution

Intuition

  • Binary Search is based on the divide and conquer strategy.
  • It works only on sorted arrays, which is a prerequisite.
  • Instead of checking each element linearly, it eliminates half of the remaining elements at each step.
  • This makes it much faster than linear search for large datasets.

Approach

  • Start with the middle element of the sorted array.
  • If the target value is equal to the middle element, return the middle index.
  • If the target value is less than the middle element, search the left half of the array.
  • If the target value is greater than the middle element, search the right half of the array.
  • Repeat steps 1-4 until the target value is found or the search interval is empty.

Complexity Analysis

  • Time Complexity: O(log n) because the algorithm divides the search interval in half at each step.
  • Space Complexity: O(1) for iterative implementation, O(log n) for recursive implementation due to the call stack.
Implementation
CPP
Run your code to see output here