Searching algorithms are essential techniques in computer science, allowing us to efficiently find specific elements within data structures like arrays and lists. Two of the most commonly taught searching algorithms are Linear Search and Binary Search.
This article will guide you through clear pseudocode examples for both methods, explain how they work, and highlight their key differences — perfect for students and beginners!
What is Linear Search?
Linear Search, also known as sequential search, is the simplest searching algorithm. It checks each element of the list one by one until the target value is found or the end of the list is reached.
Linear Search does not require the list to be sorted and is useful for small or unsorted datasets.
Pseudocode for Linear Search
1 2 3 4 5 6 7 8 9 10 11 | 1. Start 2. Input the list and the target element 3. For each element in the list: a. If the element equals the target: - Output the index (position) of the element - Stop 4. If the end of the list is reached without finding the target: - Output "Element not found" 5. End |
Example Walkthrough
Given the list [10, 20, 30, 40, 50] and target 30:
- Check 10 → Not 30
- Check 20 → Not 30
- Check 30 → Found! Output the index (2)
What is Binary Search?
Binary Search is a faster searching algorithm that works on sorted lists. It divides the list in half each time, reducing the search space by 50% with each step.
Binary Search requires the list to be sorted before searching!
Pseudocode for Binary Search
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 1. Start 2. Input the sorted list and the target element 3. Set low = 0 and high = length of list - 1 4. While low <= high: a. Set mid = (low + high) / 2 b. If list[mid] == target: - Output the index (mid) - Stop c. Else if list[mid] < target: - Set low = mid + 1 d. Else: - Set high = mid - 1 5. If the target is not found: - Output "Element not found" 6. End |
Example Walkthrough
Given the sorted list [5, 10, 15, 20, 25, 30, 35] and target 20:
- Low = 0, High = 6
- Mid = (0+6)/2 = 3 → List[3] = 20
- Target found at index 3!
Comparison: Linear vs Binary Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| List needs to be sorted? | No | Yes |
| Time Complexity (Best Case) | O(1) | O(1) |
| Time Complexity (Average/Worst Case) | O(n) | O(log n) |
| Use when | List is small or unsorted | List is large and sorted |
Conclusion
Both Linear Search and Binary Search are fundamental techniques every computer science student must master.
- Use Linear Search for unsorted or small lists.
- Use Binary Search for sorted, larger datasets where efficiency matters.
Mastering these searching algorithms — especially by understanding their pseudocode — lays a strong foundation for more complex data structures and algorithms you’ll encounter later!
