Binary Search and Its Variations
Welcome to Day 25 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Binary Search, a fundamental search algorithm, and its various variations. Binary Search is known for its efficiency in searching sorted arrays and forms the basis for many other algorithms.
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 compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target value is found.
Basic Binary Search
Here’s an implementation of the basic binary search algorithm:
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3
4 while left <= right:
5 mid = (left + right) // 2
6 if arr[mid] == target:
7 return mid
8 elif arr[mid] < target:
9 left = mid + 1
10 else:
11 right = mid - 1
12
13 return -1 # Target not found
14
15# Example usage
16arr = [1, 3, 5, 7, 9, 11, …
Binary Search and Its Variations
Welcome to Day 25 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Binary Search, a fundamental search algorithm, and its various variations. Binary Search is known for its efficiency in searching sorted arrays and forms the basis for many other algorithms.
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 compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target value is found.
Basic Binary Search
Here’s an implementation of the basic binary search algorithm:
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3
4 while left <= right:
5 mid = (left + right) // 2
6 if arr[mid] == target:
7 return mid
8 elif arr[mid] < target:
9 left = mid + 1
10 else:
11 right = mid - 1
12
13 return -1 # Target not found
14
15# Example usage
16arr = [1, 3, 5, 7, 9, 11, 13, 15]
17target = 7
18result = binary_search(arr, target)
19print(f"Target {target} found at index: {result}")
Time Complexity: O(log n)
Space Complexity: O(1)
Variations of Binary Search
1. Recursive Binary Search
A recursive implementation of binary search:
1def recursive_binary_search(arr, target, left, right):
2 if left > right:
3 return -1
4
5 mid = (left + right) // 2
6 if arr[mid] == target:
7 return mid
8 elif arr[mid] < target:
9 return recursive_binary_search(arr, target, mid + 1, right)
10 else:
11 return recursive_binary_search(arr, target, left, mid - 1)
12
13# Example usage
14arr = [1, 3, 5, 7, 9, 11, 13, 15]
15target = 11
16result = recursive_binary_search(arr, target, 0, len(arr) - 1)
17print(f"Target {target} found at index: {result}")
2. Finding the First Occurrence
Modified binary search to find the first occurrence of a target value:
1def first_occurrence(arr, target):
2 left, right = 0, len(arr) - 1
3 result = -1
4
5 while left <= right:
6 mid = (left + right) // 2
7 if arr[mid] == target:
8 result = mid
9 right = mid - 1 # Continue searching in the left half
10 elif arr[mid] < target:
11 left = mid + 1
12 else:
13 right = mid - 1
14
15 return result
16
17# Example usage
18arr = [1, 2, 2, 2, 3, 4, 4, 5]
19target = 2
20result = first_occurrence(arr, target)
21print(f"First occurrence of {target} found at index: {result}")
3. Finding the Last Occurrence
Modified binary search to find the last occurrence of a target value:
1def last_occurrence(arr, target):
2 left, right = 0, len(arr) - 1
3 result = -1
4
5 while left <= right:
6 mid = (left + right) // 2
7 if arr[mid] == target:
8 result = mid
9 left = mid + 1 # Continue searching in the right half
10 elif arr[mid] < target:
11 left = mid + 1
12 else:
13 right = mid - 1
14
15 return result
16
17# Example usage
18arr = [1, 2, 2, 2, 3, 4, 4, 5]
19target = 4
20result = last_occurrence(arr, target)
21print(f"Last occurrence of {target} found at index: {result}")
4. Finding the Floor and Ceiling
Binary search variations to find the floor (largest element smaller than or equal to target) and ceiling (smallest element larger than or equal to target):
1def floor(arr, target):
2 left, right = 0, len(arr) - 1
3 result = -1
4
5 while left <= right:
6 mid = (left + right) // 2
7 if arr[mid] == target:
8 return arr[mid]
9 elif arr[mid] < target:
10 result = arr[mid]
11 left = mid + 1
12 else:
13 right = mid - 1
14
15 return result
16
17def ceiling(arr, target):
18 left, right = 0, len(arr) - 1
19 result = -1
20
21 while left <= right:
22 mid = (left + right) // 2
23 if arr[mid] == target:
24 return arr[mid]
25 elif arr[mid] < target:
26 left = mid + 1
27 else:
28 result = arr[mid]
29 right = mid - 1
30
31 return result
32
33# Example usage
34arr = [1, 3, 5, 7, 9, 11, 13, 15]
35target = 6
36floor_result = floor(arr, target)
37ceiling_result = ceiling(arr, target)
38print(f"Floor of {target}: {floor_result}")
39print(f"Ceiling of {target}: {ceiling_result}")
5. Search in Rotated Sorted Array
A variation of binary search to find an element in a rotated sorted array:
1def search_rotated(arr, target):
2 left, right = 0, len(arr) - 1
3
4 while left <= right:
5 mid = (left + right) // 2
6 if arr[mid] == target:
7 return mid
8
9 # Check if left half is sorted
10 if arr[left] <= arr[mid]:
11 if arr[left] <= target < arr[mid]:
12 right = mid - 1
13 else:
14 left = mid + 1
15 # Right half is sorted
16 else:
17 if arr[mid] < target <= arr[right]:
18 left = mid + 1
19 else:
20 right = mid - 1
21
22 return -1 # Target not found
23
24# Example usage
25arr = [4, 5, 6, 7, 0, 1, 2]
26target = 0
27result = search_rotated(arr, target)
28print(f"Target {target} found at index: {result}")
Applications of Binary Search
- Database Systems: For efficient searching in indexed databases.
- Version Control Systems: For finding when a bug was introduced (git bisect).
- Machine Learning: In algorithms like decision trees and gradient descent.
- Computer Graphics: In ray tracing and texture mapping.
- Optimization Problems: For finding minimum or maximum values in unimodal functions.
Exercise
- Implement a binary search algorithm to find the square root of a number (up to a given precision).
- Create a function that uses binary search to find the peak element in a bitonic array (an array that first increases, then decreases).
- Implement a binary search algorithm to find the minimum element in a sorted and rotated array.
Summary
Today, we explored Binary Search and its various applications. We implemented the basic binary search algorithm and several variations, including recursive binary search, finding first and last occurrences, floor and ceiling values, and searching in rotated sorted arrays.
Binary Search is a powerful technique that forms the basis for many efficient algorithms. Its logarithmic time complexity makes it invaluable for searching large datasets. As we progress through this challenge, you’ll find binary search being used as a building block for more complex algorithms and problem-solving techniques.
Tomorrow, we’ll dive into the Quicksort algorithm, one of the most efficient sorting algorithms. Stay tuned!