Implement Searching : Linear and Binary Search


Difference Between Linear Search and Binary Search (with ...

Implement Searching : Linear and Binary Search


Prerequisites

Before learning about Linear and Binary search, we will have to need a good understanding of :-

·         Python 3
·         Data Structure in Python-lists, tuple, dictionaries and sets

Introduction

Difference between Linear search and Binary search | Geekboots

Here we will have to learn how to find an elements from the data structures like lists, linked lists and Binary trees. An efficient searching technique saves a great amount of time and improves performance.

In this tutorial we are going to learn about linear search and binary search, because this technics are very usefull to search some variables used there two searching algorithms.

Linear Search

Binary Search Trees (BST) with code in C++, Python, and Java ...

We will understand about Linear Search with a example, So let assume we want to search “Python Programming Language” Book, from a shelf in a library room how we will search it on many books ? We should start at one end, take one book at a time and check if it's Python Programming Language or not. 

We  will going to use a brute force methodology which checks every book until the Python Programming Language  is found or the end of the shelf is reached. Best case scenario would be when Python Programming Language  is the first book and worst case would be the book not in there at all.

 Either way, you can know this only by checking each and every book. This is exactly what Linear Search is.

Binary Search

Binary search tree - Wikipedia

What happened if we want to search for the Python Programming Language from the shelf of books which are ordered in alphabetically. Would we have to start searching from the start? Definitely not! You would start somewhere near the middle and check the first letter of the books and then go back or forward from there to find the 'P' titles. 

This means that you won’t be looking at all the books, after that we will saving time. You also would not need to go through the entire shelf to know whether the book is there or not. At a given point you are eliminating many books which you will never look at. Binary Search is similar to this.

NOTE :- Linear Search can be done on both sorted and unsorted items but Binary Search can only be done on a sorted set of items.

Difference Between Binary Search and Linear Search?

Linear Search Python - Learn Linear Search With Example

Even though both linear search and binary search are searching methods they have several differences. While binary search operates on sorted lists, liner search can operate on unsorted lists as well. Sorting a list generally has an average case complexity of n log n. linear search is simple and straightforward to implement than the binary search.

But, linear search is too slow to be used with large lists due to its o(n) average case performance. On the other hand, binary search is considered to be a more efficient method that could be used with large lists. But implementing the binary search could be quite tricky.

Implementation in Python

Now that you know what Linear and Binary Search methodologies are, let us look at how these searches would work on a list of numbers.

Linear Search

Given list X = [1,2,3,5,7,8,2,1,0] find if 0 is present in this list or not.

Algorithm

Take one number at a time from list X
Compare it with 0 and check if it is a match:
If yes, return True
If not, return False
If the end of the list is met, return False

Code

def linear_Search(linear,data):

for i in linear:
if i == data:
return True
return False

print(linearSearch([1,2,3,5,7,8,2,1,0] ,0))

Binary Search

The main idea in Binary Search are to  keep comparing the elements with the middle value. This way with each search we eliminate one half of the list.

Algorithm

We are going to use two pointers First and Last, these are incremented or decremented to limit the part of the list to be searched.

Find the middle element of the list: mid = ( length of the list )/2

Compare the middle element with the value to be found

Check if the middle element is lesser than the value to be found:-

·         If yes, the element must lie on the second half of the list
·         If no, the element must lie on the first half of the list

Repeat steps 1 through 3 until the element is found or the end of the list is reached

NOTE:- The list continues to get divided into two and the middle element gets compared until the element is found or no more elements are left to compare with.

Code

Given list Y = [1,2,3,5,7,8,2,1,0] find if 14 is present in this list or not.

def Binary_Search(Binary,data):
first = 0
last = len(Binary)-1
done = False  

while first<=last and not done:
mid = (first+last)//2
if Binary[mid] == data:
done = True
else:
if Binary[mid] > data:
last = last-1
else:
first = first+1
return done

print(Binary_Search([1,2,3,5,7,8,2,1,0] ,4))

NOTE:- To find the mid element, “(first+last)//2” is used instead of “(first+last)/2”. This gives us whole numbers especially when the length of the list is odd. Try 11/2 and 11//2 in your Python IDLE to get a better understanding.

Conclusion

Linear Search vs Binary Search and Why We Should Approach any ...

From the above explanation we will see that which is faster in both algorithms, it must be clear that Binary Search is consistently faster than Linear Search. If you are familiar with o(n) notation, Linear Search is o(n) and Binary Search is log(n).

You can perform Linear Searches on a sorted list as well with a small optimization. You can stop the search once the number to be found exceeds the element being compared to. For instance, you want to search for 11 from the list [1,2,3,5,7,8,2,1,0] , once you reach 12 you can stop because there is no way that 14 is going to come after 13 in a sorted list.

In this tutorial, we have discussed about only the iterative method of Binary Search. Try to implement the recursive approach on your own.  Also, learn about the uses of these searches and when to apply them. That’s all for this tutorial.

 Good Bye Friends!!


If you Guys like my tutorial plz share it with your best friends↝↜  that's all for today, 

Thank you Guys and Good Bye...

                    Related Links 

>>> Data Structure In Python    


>>> Curd Operations in Hive by Python   

>>> CGI In Python                            


>>> Create and Print Bills                   
>>> Currency Detection By Image


>>> Convert Speech To Text              
 >>> Pandas Tutorial

>>> Handling files with remote server by python 

>>> Serialization & Deserialization in C#

>>> Compare two voices by python   
Reactions

Post a Comment

0 Comments