Searching Algorithms; Algorithm Complexity Analysis

Searching Algorithms

22.1 Linear Search

Search every element from start to end.

int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;   // found at index i
    }
    return -1;  // not found
}

Complexity:

Best: O(1) (first element)
Average: O(n/2) = O(n)
Worst: O(n) (last element or not found)

Use when: Array is unsorted or very small array.

22.2 Binary Search

Requires SORTED array. Divides search space in half each step.

int binary_search(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  // avoid overflow

        if (arr[mid] == target) return mid;   // found
        else if (arr[mid] < target) low = mid + 1;   // search right
        else high = mid - 1;                          // search left
    }
    return -1;  // not found
}

Example:

Sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Search for:    23

Step 1: low=0, high=9, mid=4, arr[4]=16 < 23 → low=5
Step 2: low=5, high=9, mid=7, arr[7]=56 > 23 → high=6
Step 3: low=5, high=6, mid=5, arr[5]=23 == 23 → Found at index 5!

Complexity:

Best: O(1)
Average/Worst: O(log n)

Recursive implementation:

int binary_search_recursive(int arr[], int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;

    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) return binary_search_recursive(arr, mid+1, high, target);
    else return binary_search_recursive(arr, low, mid-1, target);
}

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Requirement	None	Sorted array
Time complexity	O(n)	O(log n)
For n=1 billion	1 billion operations	30 operations
Implementation	Simple	Slightly complex
Best for	Unsorted, small	Sorted, large

Algorithm Complexity Analysis

Big-O Notation

Big-O describes the upper bound of an algorithm's growth rate as input size n grows.

Common Complexities (Best to Worst)

Complexity	Name	Example
O(1)	Constant	Array access, hash table
O(log n)	Logarithmic	Binary search, BST search
O(n)	Linear	Linear search, tree traversal
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Bubble sort, selection sort
O(n³)	Cubic	Floyd-Warshall, matrix multiplication
O(2ⁿ)	Exponential	Recursive Fibonacci, power set
O(n!)	Factorial	Brute-force TSP

Growth Rate Comparison

n=10:      O(1) < O(log n)=3 < O(n)=10 < O(n log n)=33 < O(n²)=100 < O(2ⁿ)=1024
n=1000:    O(1)=1 < O(log n)=10 < O(n)=1000 < O(n log n)=10000 < O(n²)=1M < O(2ⁿ)=HUGE

Space Complexity

Like time complexity but for memory usage:

O(1) — uses constant extra space (in-place algorithms)
O(n) — uses space proportional to input (merge sort)
O(log n) — recursive algorithms' stack space (binary search recursive)