Solution
Search problems are computational problems where the task is to find a solution or an item that meets certain criteria. Search algorithms find specific elements (or a set of elements) within a dataset. They are used in information retrieval, database queries, and decision-making.
Linear Search
Linear search checks each item one by one until the target is found or the list ends.
- Start at the beginning of the list.
- Compare the current item with the target.
- If they do not match, move to the next item.
- Repeat until the item is found or the list is exhausted.
Example: In the list [Karachi, Lahore, Islamabad, Faisalabad], finding Islamabad requires checking Karachi, then Lahore, then Islamabad. Time grows linearly with the length of the list, so the complexity is . The list does not need to be sorted.
Binary Search
Binary Search works on a sorted list. It repeatedly divides the search interval in half.
- Start at the middle element.
- If it is the target, return its position.
- If the target is smaller, search the left half; if larger, search the right half.
Example: In the sorted list , the middle element is . The time complexity is , which grows much more slowly than linear search, especially for large datasets.
Comparison of efficiency
| Linear Search | Binary Search | |
|---|---|---|
| Requirement | Works on any list | Requires a sorted list |
| Time complexity | ||
| Large datasets | Slower; every extra item may need another comparison | Much faster; each step halves the remaining interval |
| Use | Small or unsorted data | Large sorted data (sort first if needed, for example with Merge Sort) |
Binary Search is more efficient for large datasets, provided the data is sorted.