Published in

Daily Python

# 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.

# 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 ,valdef 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)`

# 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.

# 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)`

# 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

# 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():  passdef depthFirstSearch():  passseq, val = acceptSeq(order="sorted")exponentialSearch(seq,val)`