Unit 4: Searching and sorting

• Linear search: check each element one by one until the key is found or the list ends. Works on unsorted data. Best O(1), worst O(n).
• Binary search: works only on sorted data. Compare the key with the middle element; search the left or right half; repeat. Worst case O(log n).

cint binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

Hashing stores and finds a record directly by computing its position from its key, giving average O(1) search. A hash function h(k) maps a key to an index in a hash table.

A collision happens when two keys hash to the same index.

• Open addressing (store in the table itself): linear probing (try next slots: h, h + 1, h + 2 …), quadratic probing (h + 1², h + 2² …) and double hashing (a second hash function decides the step).
• Chaining: each table slot points to a linked list of all keys that hash there.

• Bubble sort: repeatedly swap adjacent elements that are in the wrong order; the largest "bubbles" to the end each pass.
• Selection sort: find the smallest element and swap it into the first position, then the next smallest into the second, and so on.
• Insertion sort: take each element and insert it into its correct place in the already-sorted left part — efficient for nearly sorted data.
• Quick sort: choose a pivot, partition so smaller elements go left and larger go right, then sort both parts recursively (divide and conquer).