A collection of classic computer science algorithms implemented in Python — covering search, sort, numerical methods, and validation techniques.

Category: Search Algorithm
Time Complexity: O(log n) | Space Complexity: O(1)

Binary Search operates on sorted lists by repeatedly halving the search interval:

1. Set low = 0 and high = len(list) - 1.
2. Compute the midpoint mid = (low + high) // 2.
3. Compare the target value against list[mid]:
   • Equal → target found; return the index.
   • Greater → search the right half (low = mid + 1).
   • Less → search the left half (high = mid - 1).
4. Repeat until the target is found or the interval is empty.

The function also tracks the path of values checked, returning it alongside the result message.

binary_search([1, 2, 3, 4, 5], 3) # → ([3], 'Value found at index 2') binary_search([1, 3, 5, 9, 14, 22], 10) # → ([], 'Value not found')

⚠️ Prerequisite: The input list must be sorted before calling this function.

Category: Numerical Methods
Convergence: Guaranteed for continuous functions with sign changes

The Bisection Method finds the square root of a number by narrowing an interval [low, high] until the midpoint is within the desired tolerance:

1. Handle edge cases: negative numbers raise a ValueError; 0 and 1 return immediately.
2. Set low = 0 and high = max(1, target).
3. Compute mid = (low + high) / 2 and check mid² against the target:
   • If |high - low| ≤ tolerance → converged; return mid as the root.
   • If mid² < target → move low = mid.
   • Otherwise → move high = mid.
4. Repeat for up to max_iterations steps.

Accepts configurable tolerance (default 1e-7) and max_iterations (default 100).

square_root_bisection(81, 1e-3, 50) # → The square root of 81 is approximately 9.000000000000002 square_root_bisection(225, 1e-7, 10) # → Failed to converge within 10 iterations

Category: Checksum / Validation
Use Case: Credit card number validation

The Luhn Algorithm validates identification numbers (e.g., credit card numbers) via a checksum:

1. Strip all dashes (-) and spaces from the input.
2. Convert each character to an integer.
3. Starting from the second-to-last digit going right to left, double every second digit.
4. If any doubled value exceeds 9, subtract 9 from it.
5. Sum all digits. If total % 10 == 0 → VALID!, otherwise → INVALID!

verify_card_number('4111-1111-1111-1111') # → 'VALID!' verify_card_number('1234 5678 9012 3456') # → 'INVALID!'

Category: Sorting Algorithm (Divide & Conquer)
Time Complexity: O(n log n) | Space Complexity: O(n)

Merge Sort recursively splits and merges arrays in-place:

1. Divide: Split the array at the midpoint into left_part and right_part.
2. Recurse: Call merge_sort on each half.
3. Merge: Compare elements from both halves one by one, writing the smaller value back into the original array at sorted_index.
4. Append any remaining elements from either half.

The function modifies the original list in-place and returns None.

numbers = [4, 10, 6, 14, 2, 1, 8, 5] merge_sort(numbers) print(numbers) # → [1, 2, 4, 5, 6, 8, 10, 14]

Category: Sorting Algorithm (Divide & Conquer)
Time Complexity: O(n log n) average, O(n²) worst | Space Complexity: O(n)

This is a non-in-place implementation of Quicksort — it creates new lists rather than modifying the original:

1. Base case: Return the list immediately if it has 0 or 1 elements.
2. Pivot: Select the first element as the pivot.
3. Partition: Iterate over the remaining elements, distributing them into less, equal, or greater buckets.
4. Recurse & Combine: Return quick_sort(less) + [pivot] + equal + quick_sort(greater).

The original list is never modified. A new sorted list is returned.

print(quick_sort([20, 3, 14, 1, 5])) # → [1, 3, 5, 14, 20] original = [20, 3, 14, 1, 5] quick_sort(original) print(original) # → [20, 3, 14, 1, 5] ← unchanged

Category: Sorting Algorithm
Time Complexity: O(n²) | Space Complexity: O(1)

Selection Sort divides the list into a sorted and unsorted region, growing the sorted region one element at a time:

1. For each position i, scan the unsorted portion (i+1 to end) to find the index of the minimum element.
2. If the minimum is not already at position i, swap it there.
3. Advance i and repeat until the entire list is sorted.

Modifies and returns the list in-place.

print(selection_sort([33, 1, 89, 2, 67, 245])) # → [1, 2, 33, 67, 89, 245] print(selection_sort([5, 16, 99, 12, 567, 23, 15, 72, 3])) # → [3, 5, 12, 15, 16, 23, 72, 99, 567]

Each script can be run directly with Python 3:

python Binary_Search_Algorithmn.py python Bisection_Method.py python Luhn_Algorithmn.py python Merge_Sort_Algorithmn.py python Quicksort_Algorithmn.py python Selection_Sort_Algorithmn.py

No external dependencies are required — the standard Python 3 library is sufficient for all scripts.