Trusted answers to developer questions
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:
-
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.
-
If x matches with any of the elements, return the index value.
-
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:
print("x(element) is not found")
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
- Sort the list of elements.
- Find the middle element in the sorted list.
- Compare the key with the middle element
- If the key matches the middle element, print message key is found and the execution is stopped.
- 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.
- 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.
- 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:
print("key is not found")
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
Related Courses
