Sorting & Searching

Core Concepts

Binary Search: Finding an element in a sorted array in O(log n) time.
Merge Sort: A classic O(n log n) divide-and-conquer sorting algorithm.
Quick Sort: A highly efficient sorting algorithm utilizing a pivot.

graph TD A["[38, 27, 43, 3, 9, 82, 10]"] --> B["[38, 27, 43]"] A --> C["[3, 9, 82, 10]"] B --> D["[27, 38, 43] (Sorted)"] C --> E["[3, 9, 10, 82] (Sorted)"] D --> F["[3, 9, 10, 27, 38, 43, 82]"] E --> F

Cheatsheet Formulas

Binary Search: left, right = 0, len(arr) - 1. while left <= right: mid = (left + right) // 2. Check arr[mid].
Binary Search (Leftmost Insert): while left < right:. If arr[mid] < target: left = mid + 1 else right = mid.
Merge Sort Time: O(N log N) consistently. Space: O(N). Good for linked lists.
Quick Sort Time: O(N log N) average, O(N^2) worst. Space: O(log N). Best in-place array sort.

Classic Problem: Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // Prevent overflow
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return -1