Divide and conquer solves a problem by dividing it into smaller, independent subproblems, solving each subproblem, and combining their solutions. Recursive application makes the same strategy usable at progressively smaller scales. section 4.2.3 section 4.5
Apply the paradigm by following this pattern:
- Partition the original problem into smaller independent subproblems. section 4.2.3
- Solve each subproblem, recursively repeating the partition when necessary. section 1.5.2
- Combine the subproblem solutions into the solution to the original problem. section 4.5
Binary search
Given a sorted array, inspect its middle element. Stop when it matches the target or when no elements remain; otherwise continue in the left or right half selected by comparison. Halving the search space after each check gives O(log n) complexity. section 4.2.3
Listing 4.3 Binary search
def binary_search(arr, l, r, x):
#assumes a sorted array
if l <= r:
mid = int(l + (r-l) / 2)
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, l, mid-1, x)
else:
return binary_search(arr, mid+1, r, x)
#end if
else:
return -1
if __name__ == "__main__":
x = 5
arr = sorted([1, 7, 8, 3, 2, 5])
print(arr)
print("binary search:")
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("element {} is found at index {}.".format(x, result))
else:
print("element is not found.")
The implementation recursively searches a sorted Python array by adjusting the left and right bounds around the midpoint, returning an index or -1. section 4.2.3
Other examples include quick sort, merge sort, and heap sort. CART decision trees repeatedly choose a threshold, optimize a classification objective such as the Gini index, and split nodes until reaching the maximum depth. section 4.2.3 section 1.5.2
