Implementing basic searching algorithms in Python — Part 1 | Daily Python #21

This article is a tutorial on implementing basic searching algorithms in Python.

This article is a part of Daily Python challenge that I have taken up for myself. I will be writing short python articles daily.

There are no additional requirements for this article.

Searching Algorithms

Search algorithms form an important part of many programs. Some searches involve looking for an entry in a database, such as looking up your record in the IRS database. Other search algorithms trawl through a virtual space, such as those hunting for the best chess moves. Although programmers can choose from numerous search types, they select the algorithm that best matches the size and structure of the database to provide a user-friendly experience.

The general searching problem can be described as follows: Locate an element x in a list of distinct elements a1,a2,...an or determine that it is not in the list. The solution to this search problem is the location of the term in the list that equals x and is 0 if x is not in the list.

Linear Search

The linear search is the algorithm of choice for short lists, because it’s simple and requires minimal code to implement. The linear search algorithm looks at the first list item to see whether you are searching for it and, if so, you are finished. If not, it looks at the next item and on through each entry in the list.

Working of Linear Search

Linear search is the basic search algorithm used in data structures. It is also called as sequential search. Linear search is used to find a particular element in an array.

Source: GeeksforGeeks

Let’s write a function to accept a sequence of numbers

def acceptSeq(order="random"):
  seq = list(map(int,input("Enter a "+order+" sequence of numbers : ").split(" ")))
  val = int(input("Enter the value to be serached : "))
  return seq ,val

Now, let’s define a function to perform Linear Search

def acceptSeq(order="random"):
  seq = list(map(int,input("Enter a "+order+" sequence of numbers : ").split(" ")))
  val = int(input("Enter the value to be serached : "))
  return seq ,val
def linearSearch(seql,val):
  for index in range(0,len(seq)):
    print('Current Index : ',index,\
'Value at this index : ',seq[index])
if seq[index] == val:
      print('Number found at index : ',index)
      return
  print('Number not found')
seq, val = acceptSeq()
linearSearch(seq,val)

Snip of the Output of the above code snippet

Binary Search

Binary Search is one of the most fundamental and useful algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.

Binary search is a popular algorithm for large databases with records ordered by numerical key. Example candidates include the IRS database keyed by social security number and the DMV records keyed by driver’s license numbers. The algorithm starts at the middle of the database — if your target number is greater than the middle number, the search will continue with the upper half of the database. If your target number is smaller than the middle number, the search will continue with the lower half of the database. It keeps repeating this process, cutting the database in half each time until it finds the record. This search is more complicated than the linear search but for large databases it’s much faster than a linear search.

Working of Binary Search

In its simplest form, Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target or applies the search condition to the middle value of the collection; if the condition is unsatisfied or values unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with an empty half, the condition cannot be fulfilled and target is not found.

Source: GeeksforGeeks

Let’s define a function to perform Binary Search

def binarySearch(seq,val):
  start,end = 0,len(seq)-1
  while start <= end:
    mid = int((start+end)/2)
    print('Current Index : ',mid,\
          'Value at this index : ',seq[mid])
    if seq[mid] == val:
      print('Number found at index : ',mid)
      return
    elif val > seq[mid]:
      start = mid+1
    elif val < seq[mid]:
      end = mid-1
  print('Number not found ')
seq, val = acceptSeq(order="sorted")
binarySearch(seq,val)

Snip of the Output of the above code snippet

Exponential Search

Exponential search is also known as doubling or galloping search. This mechanism is used to find the range where the search key may present. If L and U are the upper and lower bound of the list, then L and U both are the power of 2. For the last section, the U is the last position of the list. For that reason, it is known as exponential.

Working of Exponential Search

Exponential search allows for searching through a sorted, unbounded list for a specified input value (the search “key”). The algorithm consists of two stages. The first stage determines a range in which the search key would reside if it were in the list. In the second stage, a binary search is performed on this range. In the first stage, assuming that the list is sorted in ascending order, the algorithm looks for the first exponent, j, where the value 2j is greater than the search key. This value, 2j becomes the upper bound for the binary search with the previous power of 2, 2j — 1, being the lower bound for the binary search

Source: wikiwand

Let’s define a function to perform Exponential Search

def exponentialSearch(seq,val):
  index = 1
  if seq[0] == val:
    print('Number found at index : 0')
    return
  while index < len(seq) and seq[index] < val:
    print('Current Index : ',index)
    index = index * 2
    print(index)
  binarySearch(seq,val)
def breadthFirstSearch():
  pass
def depthFirstSearch():
  pass
seq, val = acceptSeq(order="sorted")
exponentialSearch(seq,val)

Snip of the Output of the above code snippet

I hope this article was helpful, do leave some claps if you liked it.

Follow the Daily Python Challenge here:

Ajinkya-Sonawane/Daily-Python

Login * Instagram