CheatSheet for Searching Algorithms

CheatSheet for Searching Algorithms

1. Linear Search

int search(int arr[], int x) 
{ 
    int n = arr.length; 
    for(int i = 0; i < n; i++) 
    { 
        if(arr[i] == x) 
            return i; 
    } 
    return -1; 
} 

The time complexity of above algorithm is O(n).

---

2. Binary Search

// Returns location of key, or -1 if not found

// Returns location of key, or -1 if not found
int BinarySearch(int A[], int l, int r, int key) {
    int m;
    while( l <= r )
    {
        m = l + (r-l)/2;
        if( A[m] == key ) // first comparison
            return m;
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

The time complexity of Binary Search Theta(log(n))
Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space.

---

3. The Ubiquitous Binary Search

// Invariant: A[l] <= key and A[r] > key 
// Boundary: |r - l| = 1 
// Input: A[l .... r-1] 
int BinarySearch(int A[], int l, int r, int key) { 
    int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r-l)/2;

        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 

    if( A[l] == key ) 
        return l; 
   else if( A[r] == key ) 
        return r; 
    else
        return -1; 
}

In the while loop we are depending only on one comparison. The search space converges to place l and r point two different consecutive elements. We need one more comparison to trace search status.
The time complexity of Binary Search Theta(log(n))
Auxiliary Space: O(1)
(Some good problems)

---