Binary Search
Binary search is a powerful searching algorithm that efficiently finds the position of a target value within a sorted array. This module covers the fundamentals of binary search, its implementation, variations, and common applications.
Module Contents
Learning Resources
Introduction to Binary Search
Binary search is a divide-and-conquer algorithm that finds the position of 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.
How Binary Search Works
- Start with the middle element of the sorted array.
- If the target value equals the middle element, return the middle element's 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.
Time and Space Complexity
| Complexity | Value | Description |
|---|---|---|
| Time Complexity (Best) | O(1) | Target value is the middle element |
| Time Complexity (Average) | O(log n) | Each step eliminates half of the remaining elements |
| Time Complexity (Worst) | O(log n) | Target value is not in the array |
| Space Complexity | O(1) | Iterative implementation uses constant space |
Prerequisites
Binary search requires the array to be sorted. If the array is not sorted, you must sort it first, which would take O(n log n) time.
Implementation
Iterative Implementation in Java
// Iterative Binary Search implementation in Java
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
// Calculate middle index
// Using (left + right) / 2 can cause integer overflow
int mid = left + (right - left) / 2;
// Check if target is present at mid
if (arr[mid] == target) {
return mid;
}
// If target is greater, ignore left half
if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore right half
else {
right = mid - 1;
}
}
// Target not found
return -1;
}Recursive Implementation in Java
// Recursive Binary Search implementation in Java
public int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) {
return -1; // Target not found
}
// Calculate middle index
int mid = left + (right - left) / 2;
// Check if target is present at mid
if (arr[mid] == target) {
return mid;
}
// If target is greater, search in right half
if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
}
// If target is smaller, search in left half
return binarySearchRecursive(arr, target, left, mid - 1);
}Iterative Implementation in Python
# Iterative Binary Search implementation in Python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
# Calculate middle index
mid = left + (right - left) // 2
# Check if target is present at mid
if arr[mid] == target:
return mid
# If target is greater, ignore left half
elif arr[mid] < target:
left = mid + 1
# If target is smaller, ignore right half
else:
right = mid - 1
# Target not found
return -1Recursive Implementation in Python
# Recursive Binary Search implementation in Python
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1 # Target not found
# Calculate middle index
mid = left + (right - left) // 2
# Check if target is present at mid
if arr[mid] == target:
return mid
# If target is greater, search in right half
if arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
# If target is smaller, search in left half
return binary_search_recursive(arr, target, left, mid - 1)Variations
There are several variations of the binary search algorithm that are useful in different scenarios.
1. Finding the First Occurrence
When there are duplicate elements in the array, this variation finds the first occurrence of the target value.
// Find the first occurrence of target in a sorted array
public int findFirstOccurrence(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
// If target is found, update result and search in the left half
if (arr[mid] == target) {
result = mid;
right = mid - 1;
}
// If target is greater, search in the right half
else if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, search in the left half
else {
right = mid - 1;
}
}
return result;
}2. Finding the Last Occurrence
This variation finds the last occurrence of the target value in an array with duplicates.
// Find the last occurrence of target in a sorted array
public int findLastOccurrence(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
// If target is found, update result and search in the right half
if (arr[mid] == target) {
result = mid;
left = mid + 1;
}
// If target is greater, search in the right half
else if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, search in the left half
else {
right = mid - 1;
}
}
return result;
}3. Finding the Ceiling of a Number
The ceiling of a number is the smallest element in the array that is greater than or equal to the target.
// Find the ceiling of target in a sorted array
public int findCeiling(int[] arr, int target) {
// If target is greater than the largest element, return -1
if (target > arr[arr.length - 1]) {
return -1;
}
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// If target is found, return its index
if (arr[mid] == target) {
return mid;
}
// If target is greater, search in the right half
else if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, search in the left half
else {
right = mid - 1;
}
}
// At this point, left > right
// 'left' points to the smallest element greater than target
return left;
}4. Finding the Floor of a Number
The floor of a number is the largest element in the array that is less than or equal to the target.
// Find the floor of target in a sorted array
public int findFloor(int[] arr, int target) {
// If target is less than the smallest element, return -1
if (target < arr[0]) {
return -1;
}
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// If target is found, return its index
if (arr[mid] == target) {
return mid;
}
// If target is greater, search in the right half
else if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, search in the left half
else {
right = mid - 1;
}
}
// At this point, left > right
// 'right' points to the largest element less than target
return right;
}Interactive Binary Search Visualization
Visualizing the binary search algorithm helps in understanding how it efficiently narrows down the search space. Use the interactive visualization below to see binary search in action.
Search Steps:
- Initialized search range to [0, 14]
- Middle element is at index 7 with value 45
- Target (42) is less than middle element (45), so search left half
- New search range is [0, 6]
The visualization above demonstrates how binary search works by repeatedly dividing the search space in half. The algorithm compares the target value with the middle element of the array and eliminates half of the remaining elements in each step.
Applications
Binary search is a versatile algorithm with many practical applications beyond just searching in a sorted array.
1. Database Indexing
Binary search is used in database indexing to quickly locate records. B-trees and B+ trees, which are used in database systems, are based on the principles of binary search.
2. Finding Square Root
Binary search can be used to find the square root of a number with a specified precision.
// Find square root of a number using binary search
public double squareRoot(int num, double precision) {
double left = 0;
double right = num;
double mid = 0;
// Continue searching while the range [left, right] is valid
while (right - left > precision) {
mid = left + (right - left) / 2;
if (mid * mid > num) {
right = mid;
} else {
left = mid;
}
}
return mid;
}3. Binary Search in Rotated Sorted Array
Binary search can be modified to search in a rotated sorted array, which is a common interview question.
// Search in a rotated sorted array
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// Check if the left half is sorted
if (nums[left] <= nums[mid]) {
// Check if target is in the left half
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
// Check if target is in the right half
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}4. Binary Search on Answer
Binary search can be used to find the optimal answer in problems where the answer space is monotonic (i.e., has a clear increasing or decreasing pattern).
// Example: Find the minimum time to complete all tasks
// where each task can be assigned to any worker
public int minimumTimeToCompleteAllTasks(int[] tasks, int numWorkers) {
int left = 0;
int right = Integer.MAX_VALUE;
while (left < right) {
int mid = left + (right - left) / 2;
if (canCompleteWithinTime(tasks, numWorkers, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canCompleteWithinTime(int[] tasks, int numWorkers, int timeLimit) {
// Implementation depends on the specific problem
// Returns true if all tasks can be completed within timeLimit using numWorkers
// ...
return true; // Placeholder
}Practice Problems
Apply your knowledge of binary search by solving these carefully selected problems:
1. Binary Search
Implement binary search to find a target value in a sorted array.
2. Search in Rotated Sorted Array
Search for a target value in a rotated sorted array with no duplicates.
3. Find First and Last Position of Element in Sorted Array
Find the starting and ending position of a given target value in a sorted array.
4. Peak Index in a Mountain Array
Find the peak element in a mountain array (an array that increases and then decreases).