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