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:

  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:
        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

  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:

        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)

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)