Introduction to Binary Search
What is Binary Search?
Binary Search is a divide-and-conquer search algorithm that finds the position of a target value within a sorted array.
It works by repeatedly dividing the search interval in half, making it significantly faster than linear search with a time complexity of O(log n).
Key Characteristics
- Requires Sorted Data: The array must be sorted for binary search to work correctly
- Divide and Conquer: Repeatedly divides the search space in half
- Logarithmic Time: O(log n) time complexity, making it very efficient for large datasets
- Comparison-Based: Uses comparisons to determine which half to search next
How Binary Search Works
The basic steps of binary search are:
- Find the middle element of the array
- If the target value equals the middle element, return the middle index
- If the target value is less than the middle element, search the left half
- If the target value is greater than the middle element, search the right half
- Repeat steps 1-4 until the target is found or the search space is empty
Basic Implementation
Here's a simple implementation of binary search:
This function returns the index of the target value if found, or -1 if not found.
When to Use Binary Search
Binary search is particularly useful for:
- Searching in Large Sorted Arrays: When you need to find an element in a large sorted dataset
- Finding Insertion Points: Determining where to insert a new element in a sorted array
- Optimization Problems: Finding the minimum or maximum value that satisfies a condition
- Root Finding: Finding roots of monotonic functions
Learning Objective
Understand the fundamental concepts of binary search and its importance in efficient searching algorithms.
What is Binary Search?
Binary Search is a divide-and-conquer search algorithm that finds the position of a target value within a sorted array.
It works by repeatedly dividing the search interval in half, comparing the target value with the middle element, and eliminating half of the remaining elements in each step.
Binary search is like finding a name in a phone book. Instead of checking each page, you open to the middle, see if your target comes before or after, and eliminate half the book with each step.
Key Characteristics
Requires Sorted Data
The array must be sorted in ascending or descending order for binary search to work correctly.
Divide and Conquer
Repeatedly divides the search space in half, eliminating half of the remaining elements in each step.
Logarithmic Time
O(log n) time complexity, making it very efficient for large datasets compared to linear search's O(n).
Comparison-Based
Uses comparisons to determine which half to search next, making it adaptable to different data types.
How Binary Search Works
1Find Middle
Calculate the middle index of the current search range.
2Compare
Compare the target value with the middle element.
3Found?
If equal, return the middle index as the target is found.
4Eliminate Half
If target is less, search left half; if greater, search right half.
5Repeat
Repeat until target is found or search space is empty.
Basic Implementation
Here's a simple implementation of binary search:
1234567891011121314151617181920212223242526function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left <= right) { // Find the middle index const mid = Math.floor((left + right) / 2); // Check if target is found if (arr[mid] === target) { return mid; } // If target is less than mid, search left half if (arr[mid] > target) { right = mid - 1; } // If target is greater than mid, search right half else { left = mid + 1; } } // Target not found return -1;}Note: The condition left >= right ensures we check all elements. When left > right, the search space is empty, meaning the target is not in the array.
Time and Space Complexity
Time Complexity
O(log n), where n is the number of elements in the array.
With each step, we eliminate half of the remaining elements, leading to a logarithmic time complexity. For example, in an array of 1,000,000 elements, binary search would require at most 20 comparisons.
Space Complexity
O(1) for iterative implementation, O(log n) for recursive implementation.
The iterative implementation uses a constant amount of extra space regardless of input size. The recursive implementation uses space proportional to the depth of the recursion, which is log n.
When to Use Binary Search
Good Use Cases
- Searching in large sorted arrays
- Finding insertion points in sorted arrays
- Optimization problems with monotonic functions
- Root finding for monotonic functions
Limitations
- Requires sorted data (sorting may add O(n log n) overhead)
- Not suitable for linked lists (requires random access)
- May not be worth the implementation complexity for small arrays
- Requires careful implementation to avoid integer overflow