Heyy, how is it going? Hope you guys are doing great😊. Welcome to another lesson from NCP. Today we will be learning about two different types of search algorithms.
Are you looking for something? Does searching a large chunk of data seem troublesome? Well, worry no more, because today we will be learning to use an algorithm to search any amount of data for us. Searching something could be a problem that you may come across quite frequently. And as you know, one of the biggest reasons to learn programming is making our life easier. In this article, we will be looking at two ways/methods/algorithms that can help you search an element quicker.
WHY WOULD YOU NEED AN ALGORITHM TO SEARCH SOMETHING?
The answer is quite simple, algorithms are faster, more efficient and accurate. Searching a small amount of data should not be a big deal for us, but if you are looking for a needle in a haystack, you might need an algorithm. Let’s say you are looking for a particular number in a series of 5 numbers. Quite simple right? Anyone can just take a look and tell you if the number exists in the series or not.
But let us just say, you are looking for a specific three-digit number in a randomly arranged series of numbers ranging from 100-999. This is where algorithms can prove to be way more efficient than an average human. While it is still possible, it will take a lot longer for an average person to find the number than for an algorithm to do the same.
TYPES OF SEARCH ALGORITHMS:
There are two methods to look for a particular element in a list of data:
- LINEAR SEARCH: If you are familiar with loops and iterables this could be the first solution that comes to your mind. It is totally correct! You can use a loop to iterate through the list and look for the number.
Basically the loop will go through the list while looking for the number by matching the number you are looking for and the current position of the loop in the list. If it finds the number, it will return the number and where it found the number in the list. If in case it doesn’t find the number in the list, it will not return anything and the program will terminate telling you that it couldn’t find the number in the list.
This is how a linear search program would look like:
def lin_search(n, nums):
for i in nums:
if nums[i] == n:
print(“Found {} at index number {}”.format(n, i))
return
print(“Couldn’t find {} in the list !”.format(n))
nums = range(0, 100)
lin_search(25, nums)
In this program, we have defined a function ‘lin_search’ which accepts two parameters, ‘n’, which is the number you are looking for, and ‘nums’, which is the list you want to conduct the search in. The for loop goes through each number in the list and tries to find the number you are looking for. If it finds the number, it will print a statement telling you that the number was successfully found in the list and terminate the program by returning.
If the loop doesn’t find your number, it will print a negative statement telling you that it couldn’t find the number in the list.
- BINARY SEARCH: This is a more efficient way to search something. How is more efficient? It reduces the execution time, which is quite a big deal when you are working on big projects and programs which in general have a higher execution time. The basic concept of the binary search is that it searches your number by dividing the list into two halves and searching for it in the half that is more likely to have the number. For example, if you have a list of numbers, the first thing the program will do is sort the numbers. Sorting is process of rearranging the numbers in either ascending or descending order. Let us assume we have the following list:
nums = [5, 8, 3, 2, 7, 1, 6, 4]
As you can see, we have a list of eight shuffled numbers i.e. the numbers are not arranged following any particular pattern. Here, our first step should be to arrange the numbers in either ascending or descending order. I’ll be arranging the numbers in ascending order for this example. The following code will sort the list for us:
nums.sort()
Now, my ‘nums’ list should look like this:
nums = [1, 2, 3, 4, 5, 6, 7, 8]
Now, we have an arranged list and we can start our binary search. Here is how it is going to work, our algorithm will try to find the middle element in the list by diving the adding the position of the first and the last element and then dividing the sum by 2, if the result is not a whole number, we will round down the result to get a whole number. Once we get the position of the middle element in the list, we will check if that is the element we are looking for. If it is, the program ends and it prints that the element is found. If it is not the element we are looking for, the algorithm continues.
Once, the algorithm has established that the middle element is not what we are looking for. It will check if the element we are looking for is greater than or less than the middle element.
Let us say, we are looking for the number ‘8’ in the ‘nums’ list above. The index value of the first element in the list will be 0 and of the last element will be 7 (in this case). The index value of the middle element should be 7/2 = 3.5, but since we are looking for a whole number, we will round down this value. So the index number of the middle element is 3. The value of nums[3] = 4. Since, 4 is not the number we are looking for the algorithm continues. We will now see if the number we are looking for is greater than or less than 4. It can be easily established that 8 is greater than 4. Therefore, the algorithm will eliminate the lower half of the list and only look at the upper half.
[5, 6, 7, 8], this is what the program is looking at. The middle element of this new list is ‘6’. ‘6’ is not the number we are looking for. Therefore, the algorithm continues. It eliminates ‘6’ and ‘5’ from the list and is now looking at the remaining two numbers.
Since, ‘7’ is at index value 6 and ‘8’ is at index 7, we get the middle element to be ‘7’ ((6 + 7)/2 = 6.5, which when rounded down is 6). ‘7’ is not our number and so the algorithm checks the last number in the list which is ‘8’, which is the number we were looking for. The program prints the number was found in the list and programs terminates.
It took us 3 iterations to go through the list and find our number with binary search. If we were to use linear search however, it would take us 8 iterations.
This is what our program should look like in the end:
def binary_search(nums, item):
nums.sort()
first = 0
last = len(nums) – 1
found = False
while first <= last and not found:
mid = (first + last)//2
if nums[mid] == item:
found = True
else:
if item < nums[mid]:
last = mid – 1
else:
first = mid + 1
return found
nums = [5, 8, 3, 2, 7, 1, 6, 4]
item = 8
if binary_search(nums, item):
print(“The item is in the list”)
else:
print(“The item is not in the list”)
In this program, we are looking for the number in the variable ‘item’ in the list ‘nums’. ‘first’ stores the index value of the first element in the list which is 0 and ‘last’ stores the index of the last element which is the length of the list – 1. The values of ‘first’ and ‘last’ may change as we proceed in the program.
The while loop runs as long as ‘first’ is less than equal to ‘last’ (which tells us there is at least one element in the list) and the ‘item’ is not found in the list.
We find the middle element by adding the index of the first and last element and dividing the resulting sum by 2. If the middle element is equal to ‘item’ the programs sets ‘found’ as True. Otherwise, the program continues by checking if the middle element is greater than ‘item´ or less than ‘item’. In case of the former, ‘first’ is set to ‘mid + 1’ to eliminate the lower half and if the middle element is less than ‘item’, ‘last’ is set to ‘mid – 1’ to eliminate the upper half and the program continues.
Finally, ‘found’ is returned which tells us if the item was found in the list or not.
CONCLUSION:
CONGRATULATIONS!!! You have now learnt a more efficient way to search an item in a sorted list. In the above example, binary search was able to find the item in about half the amount of iterations a linear search would take to do the same. This kind of efficiency can be really helpful to you in the future because in large programs, every split second counts. Can you come up with a more efficient and easy way to search for an item in the list? Let me know in the comments down below ;)
If you loved it, hated it or have any other sort of feedback head down to the comments section below and tell me how you feel. Also, if you have any queries regarding the topics taught in this lesson or previous lessons, you can always find me in the comments section or in the telegram channel or on my pinterest profile where you can personally talk to me and ask me any question about anything we have learnt so far.
So, this was how you can create a new
system build to execute your interactive python programs. Stay tuned for
another article next week, same time, where we will discuss about some
algorithms, what they are, how they work and where you use them. So more
cool stuff coming your way, DON’T MISS IT !! And I'll see you next week.
Goodbye and Good Luck :)
I hope this article answered all of
your questions and even helped you in becoming a better programmer. IF IT DID,
leave a like AND FOLLOW THIS BLOG TO BECOME A PROFESSIONAL PYTHON PROGRAMMER FROM A TOTAL
BEGINNER. IF IT DIDN'T, feel free to ask any further queries in the comment
section below.
If you are a beginner, intermediate, advanced or just someone interested
in programming, feel free to join our telegram channel and be among people like
you:
https://t.me/joinchat/AAAAAFVduJs3bF00nwKGUA
And do you know the best part? Joining it is FREE !!!
So go ahead click on the link and I will see you there.
You can also contact me through my email: code2learnofficial@gmail.com
or
HOPE YOU HAVE AN AWESOME DAY AHEAD !!!
0 Comments
Welcome to the comments section, this is where you can contact me personally for any doubts or feedback