1. Core Concepts Binary search is the standard algorithm for locating a specific element in a sorted sequence. It operates on the divide-and-conquer principle.
Mechanism: Repeatedly halves the search space. By comparing the target with the middle element, we eliminate half of the candidates instantly. Prerequisite: The sequence must be sorted (monotonic). Complexity: Time: $O(\log n)$ (Dramatically faster than the $O(n)$ of linear search). Space: $O(1)$ (Iterative implementation). 2. Python’s bisect Module implementing binary search manually is error-prone (off-by-one errors are common). Python’s bisect module provides a standardized, robust C-optimized implementation.
Read note →Quicksort is a Divide and Conquer algorithm.
Divide (Pick Pivot): Choose one element from the array to be the pivot. Conquer (Partition): Rearrange the array so that the pivot is in its final sorted position. All elements smaller than the pivot are placed to its left, and all elements greater than the pivot are placed to its right. (Elements equal to the pivot can go on either side, depending on the scheme). Combine (Recurse): Recursively apply the same strategy to the two smaller subarrays—the one to the left of the pivot’s new position and the one to the right. The “combine” step is trivial as the sorting happens in place. def partition(a, left, right): """ Partitions the subarray a[left...right] using the Lomuto scheme with a[left] as the pivot. Returns the final index of the pivot. """ # The pivot is the first element pivot_value = a[left] # 'idx' will track the boundary of the 'less-than-or-equal-to' partition. # All elements at indices [left+1 ... idx-1] will be <= pivot. idx = left + 1 # Iterate through the array to partition it for i in range(left + 1, right + 1): # If current element is smaller or equal to the pivot if a[i] <= pivot_value: # Move it to the 'less-than' partition a[idx], a[i] = a[i], a[idx] # Expand the 'less-than' partition idx += 1 # At the end, swap the pivot (originally at a[left]) with # the last element of the 'less-than' partition (at a[idx - 1]) # to put the pivot in its final sorted position. pivot_final_index = idx - 1 a[left], a[pivot_final_index] = a[pivot_final_index], a[left] return pivot_final_index def quicksort(a, left, right): """ Sorts the array 'a' in-place from index 'left' to 'right' using the quicksort algorithm. """ if left < right: # Partition the array and get the pivot's final index pivot_index = partition(a, left, right) # Recursively sort the two subarrays quicksort(a, left, pivot_index - 1) # Subarray to the left of pivot quicksort(a, pivot_index + 1, right) # Subarray to the right of pivot
Read note →The algorithm breaks the problem down into smaller, manageable pieces and then reassembles them in a sorted order. This happens in three main phases:
Divide: The list is repeatedly divided in half until you are left with many small lists, each containing only one element. A list with one element is considered, by definition, to be sorted (this is the base case for the recursion). Conquer: This phase is trivial. Since the base-case lists (of one element) are already sorted, there’s no work to do. The real work happens in the “Combine” step. Combine (The “Merge”): This is the core of the algorithm. Merge sort begins to combine (or “merge”) the small, one-element lists back together, two at a time. Crucially, it merges them in sorted order. It then takes those newly sorted lists (now of 2 elements) and merges them together, and so on, until the entire list is reassembled into one final, sorted list. def merge_sort(arr): """ Sorts a list in ascending order using the merge sort algorithm. """ # Base case: A list with 0 or 1 elements is already sorted if len(arr) <= 1: return arr # 1. Divide: Split the list into two halves mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] # 2. Conquer: Recursively sort each half sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) # 3. Combine: Merge the two sorted halves merged = [] i = 0 # Pointer for sorted_left j = 0 # Pointer for sorted_right # Loop while both halves have elements to compare while i < len(sorted_left) and j < len(sorted_right): if sorted_left[i] < sorted_right[j]: merged.append(sorted_left[i]) i += 1 else: merged.append(sorted_right[j]) j += 1 # At this point, one of the halves is empty. # Add all remaining elements from the non-empty half. merged.extend(sorted_left[i:]) merged.extend(sorted_right[j:]) return merged # --- Example Usage --- my_list = [38, 27, 43, 3, 9, 82, 10] print(f"Original list: {my_list}") sorted_list = merge_sort(my_list) print(f"Sorted list: {sorted_list}")
Read note →