Scribd
Upload
2 views4 pages

Searching Algorithm in Python

The document explains two searching algorithms in Python: Linear Search and Binary Search. Linear Search checks each element in a list sequentially until the desired element is found, while Binary Search operates on a sorted list by dividing it into partitions to locate the element more efficiently. Examples of both methods are provided, demonstrating how to implement them in Python code.

Uploaded by

shabangumanqoba17
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views4 pages

Searching Algorithm in Python

The document explains two searching algorithms in Python: Linear Search and Binary Search. Linear Search checks each element in a list sequentially until the desired element is found, while Binary Search operates on a sorted list by dividing it into partitions to locate the element more efficiently. Examples of both methods are provided, demonstrating how to implement them in Python code.

Uploaded by

shabangumanqoba17
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Searching algorithm in python

Searching is used to find the location where an element is


available. There are two types of search techniques. They are:

1. Linear or sequential search


2. Binary search

Linear Search
This is the simplest of all searching techniques. In this
technique, an ordered or unordered list will be searched one by one
from the beginning until the desired element is found. If the desired
element is found in the list then the search is successful otherwise
unsuccessful.

Example
Suppose we have the following unsorted list.

Elements 90 70 80 10 50 20 40 30 100 60
Index 0 1 2 3 4 5 6 7 8 9

Searching different elements is as follows:


1. Searching for x = 40 Search successful, data found at 6th
position.
2. Searching for x = 90 Search successful, data found at 0th
position.
3. Searching for x = 55 Search un-successful, data not found.

Example
def linear_search(item):
pos = 0
list=[90,70,80,10,50,20,40,30,100,60]
for i in list:
if i == item:
print 'element is found at index',pos
else:
pos = pos + 1

linear_search(40)
linear_search(90)
Output
element is found at index 6
element is found at index 0

Binary Search
The binary search approach is different from the linear search.
The binary search technique is used to search for a particular
element in a sorted array or list. In this technique, two partitions of
lists are made and then the given element is searched and hence, it
is known as binary search.

Example
Suppose we have the following sorted list.

Elements 10 20 30 40 50 60 70 80 90 100
Index 1 2 3 4 5 6 7 8 9 10

The number of comparisons required for searching different


elements is as follows:

If we are searching for x = 20: (This needs 2 comparisons)


low = 1, high = 10, mid = 11/2 = 5, check 50
low = 1, high = 4, mid = 5/2 = 2, check 20,found

If we are searching for x = 80: (This needs 2 comparisons)


low = 1, high = 10, mid = 11/2 = 5, check 50
low = 6, high = 10, mid = 16/2 = 8, check 80,found
Example
def binary_search(x):
list = [10,20,30,40,50,60,70,80,90,100]
l=0
r=len(list)-1
while l <= r:
mid = (l +r)/2;
if list[mid] == x:
print 'Element is found at index',mid
return 0
elif list[mid] < x:
l = mid + 1
else:
r = mid - 1
binary_search(20)
binary_search(80)
Output
Element is found at index 1
Element is found at index 7

You might also like