Searching & Sorting Algorithms

🔍 Searching Algorithms

Linear Search

Linear search checks each element in the array sequentially until the target is found or the end is reached. Time Complexity: O(n) | Space Complexity: O(1)

Java Implementation:

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;  // Return index if found
        }
    }
    return -1;  // Return -1 if not found
}

When to use: Works on both sorted and unsorted arrays. Best for small datasets or when data is unsorted.

Binary Search (Iterative)

Binary search repeatedly divides the sorted array in half, comparing the middle element with the target. Time Complexity: O(log n) | Space Complexity: O(1)

Java Implementation:

public int binarySearchIterative(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // Found at index mid
        } else if (arr[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }
    return -1;  // Not found
}

Prerequisite: Array must be sorted. Much faster than linear search for large datasets.

Binary Search (Recursive)

Recursive implementation of binary search using the divide-and-conquer approach. Time Complexity: O(log n) | Space Complexity: O(log n) due to recursion stack

Java Implementation:

public int binarySearchRecursive(int[] arr, int target, int left, int right) {
    // Base case: element not found
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    // Base case: element found
    if (arr[mid] == target) {
        return mid;
    }
    
    // Recursive cases
    if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

// Helper method to call with initial parameters
public int binarySearch(int[] arr, int target) {
    return binarySearchRecursive(arr, target, 0, arr.length - 1);
}

Note: Recursive version is more elegant but uses extra memory for the call stack.

📊 Sorting Algorithms

Bubble Sort

Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if they're in the wrong order. Time Complexity: O(n²) | Space Complexity: O(1)

Java Implementation:

public void bubbleSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        
        // Last i elements are already sorted
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        // If no swaps occurred, array is sorted
        if (!swapped) {
            break;
        }
    }
}

Optimization: The boolean flag stops early if the array becomes sorted before all passes complete.

Selection Sort

Selection sort divides the array into sorted and unsorted regions. It repeatedly selects the minimum element from the unsorted region and moves it to the sorted region. Time Complexity: O(n²) | Space Complexity: O(1)

Java Implementation:

public void selectionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        // Find minimum element in unsorted portion
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap minimum element with first unsorted element
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

Advantage: Makes minimum number of swaps (at most n-1), useful when writing to memory is costly.

Insertion Sort

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position. Time Complexity: O(n²) worst case, O(n) best case | Space Complexity: O(1)

Java Implementation:

public void insertionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // Insert key at correct position
        arr[j + 1] = key;
    }
}

Best for: Small datasets or nearly sorted arrays. Very efficient when data is almost sorted.

🎯 Practice Problems

📋 Algorithm Comparison

Algorithm	Best Case	Average Case	Worst Case	Space
Linear Search	O(1)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)