Linear Search

Searches from 0 to n-1 (linearly)
Time Cost: O(n)

1
2
3
4
5
6
7
8

bool linear_search(int array[], int length, int x) {
    for (int i = 0; i < length; i++) {
        if (array[i] == x) {
            return true;
        }
    }
    return false;
}

Linear Search (ordered data)

Searches from 0 to n-1 (linearly)
if (x > array[i]) break;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int linear_search_ordered(int array[], int length, int x) {
    for (int i = 0; i < length; i++) {
        if (array[i] == x) {
            return true;
        }
        else if (array[i] > x) {
            return false;
        }
    }
    return false;
}

Binary Search (ordered data)

  • divide and conquer
  • start at the middle; and we can check which side to continue checking

best case: t(n) ~ O(1)
worst case: t(N) = 1 + t(N/2) = log2(N) + 1 ~= O(log N)