Trusted answers to developer questions
How to search in Python
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)breakelse:print("x(element) is not found")lst=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]x=7print(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=0last=len(lst)-1flag= Falsewhile (first<=last and not flag):mid= (first + last)//2if lst[mid] == x:flag=Trueelif x>lst[mid]:first= mid +1else:last = mid-1if 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 = 7print("the element needed to search, x =",x)BinarySearch(lst,x)
RELATED TAGS
linear search
binary search
python
CONTRIBUTOR
Abhishek PusuluriTRENDING TOPICS
Did you find this helpful?