The Search for Data

Searching is one of the most fundamental tasks in computing. Whether you are looking for a name in a contact list or a specific record in a database, you are using a search algorithm.

1. Linear Search (Sequential Search)

The simplest way to search. You start at the beginning of the array and check every single element until you find a match or reach the end.

• Time Complexity: O(n) - In the worst case, you check every item.
• Best for: Small, unsorted arrays.

int linearSearch(int arr[], int size, int target) {
    for(int i = 0; i < size; i++) {
        if(arr[i] == target) return i; // Found!
    }
    return -1; // Not found
}

2. Binary Search (Divide and Conquer)

Much faster than linear search, but it ONLY works on sorted arrays. It works by repeatedly dividing the search interval in half.

• How it works:

1. Check the middle element.
2. If it's the target, done!
3. If the target is smaller, repeat on the left half.
4. If the target is larger, repeat on the right half.

• Time Complexity: O(log n). This is incredibly fast. Finding an item in a list of 1 million items takes only about 20 steps!

Linear vs. Binary Search

Always sort your data if you plan to search through it many times. The one-time cost of sorting will be paid back by the lightning speed of binary search!