Related Tags

linear search
binary search
python
community creator

# How to search in Python

Abhishek Pusuluri

## Searching algorithms

Searching algorithms are used to retrieve or search any element from a given data structure set.

Based on the methods, the searching algorithms are classified into 2 types:

1.Linear search

2.Binary search

## Linear search

• A method used to find a particular element or value in a list or an array by traversing through each and every element sequentially, until the desired element is found.

• Also known as sequential search.

## Algorithm/procedure for linear search:

1. Starts from the leftmost element of given array or list and, one by one, compares element x with each element of the array or list.

2. If x matches with any of the elements, return the index value.

3. If x doesn’t match with any of elements in the list or array, return -1 or element not found.

def LinearSearch(lst,x):
for i in range(len(lst)):
if x == lst[i]:
print("x(element) is found at the index=",i)
break
else:
lst=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x=7
print(lst)
print("The element needed to search, x =",x)
LinearSearch(lst,x)

## Binary search

• Also known as interval search
• More efficient than linear search.
• Uses the divide and conquer search algorithm

## Algorithm/procedure for binary search

1. Sort the list of elements.
2. Find the middle element in the sorted list.
3. Compare the key with the middle element
4. If the key matches the middle element, print message key is found and the execution is stopped.
5. Else, if the key is greater than the middle element, the key is searched for in the right sublist and starts again with the step 3.
6. Else, if the key is smaller than the middle element, the key is searched for in the left sublist and starts again with step 3.
7. If the key is still not matched, return the message key that was not found.
def BinarySearch(lst,x):
first=0
last=len(lst)-1
flag= False
while (first<=last and not flag):
mid= (first + last)//2
if lst[mid] == x:
flag=True
elif x>lst[mid]:
first= mid +1
else:
last = mid-1
if flag == True:
print("Key is found")
else:
lst=[1, 3, 4, 5, 8, 9, 6, 10, 7]
lst.sort()
print(lst)
x = 7
print("the element needed to search, x =",x)
BinarySearch(lst,x)

RELATED TAGS

linear search
binary search
python
community creator

CONTRIBUTOR

Abhishek Pusuluri
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time