Search Algorithms
In the realm of computer science, efficiently finding data is crucial. Search algorithms are the tools that make this possible. This post delves into two fundamental search algorithms: linear search and binary search.
Linear Search
Imagine searching for a specific item in a row of objects; you start at one end and check each object until you find it.
For instance, if you're looking for the number 6 in different lists, where you find it first depends on its position in each list. In linear search, the speed of finding your item depends on its location in the list.
List-A
List-B
In this case, List-B would be faster for a linear search to find the number 6, as it appears first in the sequence. The linear search is straightforward and efficient for shorter lists, but its speed varies based on the position of the target item.
Binary Search
Binary search requires that the list is already sorted. As the name indicates, binary search is a process of splitting a sorted list into halves to narrow down to the last match.
Example-1:
Let's say players A and B are playing a number guessing game.
A: Guess the number that I'm thinking about from numbers 1 to 20 inclusive.
B: Hmmm... Let's see. How about 2?
A: Higher!
Was picking 2 a good guess? No. Player B could have eliminated half of the numbers if he/she had mentioned 10! Let's try that again.
A: Guess the number that I'm thinking about from numbers 1 to 20 inclusive.
B: How about 10?
A: Higher!
Now, what would be the next good guess that would eliminate half of what is left?
B: Hmm.. half of 10 and 20 would be 15. So, 15.
A: Lower!
B: So now the number range is from 10 to 15 inclusive. So the middle number would be 13. 13!
A: Lower!
B: The range is 10 to 13. How about 12?
A: Correct!
Example-2:
Using binary search, let's see if the List contains 6. Note: The list is sorted.
1st try:List
Is the middle number in the List larger than 6?>> Yes>>> Discard middle (7) and up.
2nd try:
Is the middle number larger than 6?>>No>>>Discard middle (3) and below
3rd try:
Is the middle number larger than 6?>> No>>> Discard middle number.So we can conclude that number 6 is NOT in the List.
Linear vs Binary Search: Which is more efficient?
While linear search is a straightforward method that checks each element sequentially, binary search offers a more efficient approach by dividing and conquering, significantly reducing the search time in sorted arrays.
For more resources: