To understand and implement divide-and-conquer algorithms: Binary Search, Merge Sort, and Quick Sort, and analyze their time and space complexities.
Table of contents
Open Table of contents
1. Binary Search
Binary Search is a divide-and-conquer algorithm used to efficiently locate a target element in a sorted array. By repeatedly halving the search interval, the algorithm significantly reduces the number of comparisons needed compared to linear search.
def binary_search(arr, target, low, high):
if low > high:
return -1 # Element not found
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
Complexity Analysis
- Best-case time complexity: \(\Omega(1)\)
(if the target is found in the middle on the first try) - Average-case time complexity: \(\Theta(\log n)\)
- Worst-case time complexity: \(O(\log n)\)
- Space Complexity:
- \(O(1)\) if implemented iteratively
- \(O(\log n)\) if implemented recursively (due to recursion stack)
2. Merge Sort
Merge Sort is a stable, divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves back together. This algorithm is renowned for its predictable (\Theta(n \log n)) time complexity in all cases.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
sorted_arr = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
return sorted_arr + left[i:] + right[j:]
Complexity Analysis
- Time Complexity:
- Best-case: \(\Theta(n \log n)\)
- Average-case: \(\Theta(n \log n)\)
- Worst-case: \(\Theta(n \log n)\)
- Space Complexity: \(O(n)\)
(additional space is required for merging)
3. Quick Sort
Quick Sort is an in-place divide-and-conquer sorting algorithm that selects a pivot element, partitions the array into subarrays of elements less than and greater than the pivot, and then recursively sorts the partitions. Its efficiency greatly depends on the choice of pivot.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
Complexity Analysis
- Time Complexity:
- Best-case: \(\Theta(n \log n)\)
(balanced partitioning) - Average-case: \(\Theta(n \log n)\)
- Worst-case: \(O(n^2)\)
(when the pivot results in highly unbalanced partitions)
- Best-case: \(\Theta(n \log n)\)
- Space Complexity:
- Average-case: \(\Theta(\log n)\) (due to recursion depth)
- Worst-case: \(O(n)\) (in the case of highly unbalanced recursion)
All Together
# 1. Binary Search
def binary_search(arr, target, low, high):
if low > high:
return -1 # Not found
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
# 2. Merge Sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
sorted_arr = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
return sorted_arr + left[i:] + right[j:]
# 3. Quick Sort
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Merge Sort:", sorted_arr)
sorted_arr = quick_sort(arr)
print("Quick Sort:", sorted_arr)
index = binary_search(sorted_arr, 9, 0, len(sorted_arr) - 1)
print("Binary Search (9 found at index):", index)
Conclusion
Divide-and-conquer algorithms like Binary Search, Merge Sort, and Quick Sort form the backbone of efficient algorithm design. Binary Search provides rapid search capabilities in sorted arrays, Merge Sort guarantees stable and predictable performance, and Quick Sort, while generally efficient, requires careful pivot selection to avoid worst-case scenarios. Mastery of these techniques is essential for both theoretical understanding and practical application in computer science.
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
Introduction to Algorithms, 3rd/4th Edition, MIT Press.