Search Algorithms

Sequence Search

Sequence search, also known as linear search, is a search algorithm that traverses and compares elements in their original order.

For any sequence and an element to find (the key), compare the key with each element in the sequence until an element equal to the given key is found or every element has been compared. If an element equals the key, the search succeeds. If no element equals the key through the last element, the search fails.

In the best case, the key is found in the first position, and the time complexity is $O(1)$. In the worst case, the key does not exist and $n$ comparisons are required, giving a time complexity of $O(n)$.

typedef int T;

int sequence_search(T *arr, int n, T key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

Binary Search

Binary search, also known as half-interval search, is a highly efficient search method. It requires the linear list to use sequential storage and its elements to be ordered by key.

The algorithm assumes that the elements are arranged in ascending order and compares the key at the middle position with the search key. If they are equal, the search succeeds. Otherwise, the middle record divides the list into two sublists. If the middle key is greater than the search key, the search continues in the first sublist; otherwise, it continues in the second. This process repeats until a matching record is found or no sublist remains, in which case the search fails.

The time complexity of binary search is $O(\log n)$.

typedef int T;

int binary_search(T *arr, int n, T key) {
    int start = 0;
    int end = n - 1;

    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}