Searching Algorithms on Python Lists

Searching algorithms are methods to search or traverse data structures to retrieve particular data. Based on the way the data is searched for, searching algorithms can be divided into two types

  • Sequential Search - Here each data in the data structure is traversed sequentially till the target element is reached. If not found, all the elements in the data structure are traversed. For example, Linear Search.
  • Interval Search - These are specially designed for data structures with elements stored in order ie. sorted. These are much more efficient than Sequential ones. They repeatedly divide the data structure into halves to reduce the area of search. For example, Binary Search.

Linear Search using Python

Linear Search is a Sequential Search Algorithm that traverses each and every element in the data structure until and unless it reaches the searched data. If it traverses all the data present, then the searched data is not present in the data structure.
linear-search

The time complexity of Linear Search is O(n). The worst-case time complexity is also O(n).

Linear Search Algorithm

Assumptions: 'array' is an array of 10 elements.

LinearSearch( arguments: array, search_element )

  1. Start
  2. Input array
  3. Input search_element
  4. i <- 0
  5. While i < = length of array do
    1. If search_element = array [ i ] then
      1. Return i
    2. EndIf
    3. i <- i + 1
  6. EndWhile
  7. Return -1
  8. Stop

Linear Search Code using Python

The Linear Search Algorithm is implemented in Python 3 code as follows.

def LinearSearch(array, element):
    i = 0
    while i < len(array):
        if array[i] == element:
            return i
        i = i + 1
    return -1

The compiled and implemented program as follows

def LinearSearch(array, element):
    i = 0
    while i < len(array):
        if array[i] == element:
            return i
        i = i + 1
    return -1


array1 = [1, 2, 3, 5]
value1 = 3
value2 = 7
if LinearSearch(array1, value1) != -1:
    print("The element is found at ", LinearSearch(array1, value1))
else:
    print("The element is not present in the array")
if LinearSearch(array1, value2) != -1:
    print("The element is found at ", LinearSearch(array1, value2))
else:
    print("The element is not present in the array")

the output

The element is found at  2
The element is not present in the array
Advantages
  • Small and medium arrays can be searched quickly
  • Less memory overhead
  • Easier to understand
Disadvantages
  • Takes more time to search large datasets and arrays
  • All the elements are traversed
  • Very slow to process
  • Used to search small arrays
  • Used to search in Linked Lists

Binary Search using Python

Binary Search is an Interval Search Algorithm that is applied on ordered or sorted arrays to search for elements. It repeatedly divides the array on the basis of the value to be searched, and the section of the array, that particular value might be present in.

The algorithm calculates the middle index element of that interval and compares it with the value to be searched. If the value is greater than the middle index element, then the starting index for choosing the middle index is updated. Otherwise, if the value is smaller, the ending index is updated.

This process keeps on rolling until the interval is either empty, or the value is found.

Step 1

binary-search-step-1

Step 2

binary-search-step-2

Step 3

binary-search-step-3

Step 4

binary-search-step-4

Step 5

binary-search-step-5

Step 6

binary-search-step-6

The time complexity of Binary Search is O(Log n).

Binary Search Algorithm

Assumptions: 'array' is an array with numerical data.

BinarySearch( Arguments: array, start, stop, search_element )

  1. Start
  2. If stop < start then
    1. Return -1
  3. EndIf
  4. mid <- ( start + stop ) / 2
  5. If array[ mid ] < search_element then
    1. Call BinarySearch( parameters: array, mid + 1, stop, search_element )
  6. Else If array[ mid ] > search_element then
    1. Call BinarySearch( parameters: array, start, mid - 1, search_element )
  7. Else
    1. Return mid
  8. EndIf
  9. Stop

Binary Search Code using Python

The Python 3 code to implement the Binary Search algorithm is as follows

def BinarySearch(array, start, stop, element):
    mid = int((start + stop)/2)
    if stop < start:
        return -1
    if array[mid] < element:
        return BinarySearch(array, mid + 1, stop, element)
    elif array[mid] > element:
        return BinarySearch(array, start, mid - 1, element)
    else:
        return mid

The compiled and implemented code is

def BinarySearch(array, start, stop, element):
    mid = int((start + stop)/2)
    if stop < start:
        return -1
    if array[mid] < element:
        return BinarySearch(array, mid + 1, stop, element)
    elif array[mid] > element:
        return BinarySearch(array, start, mid - 1, element)
    else:
        return mid

array1 = [1, 2, 3, 5]
value1 = 3
value2 = 7
if BinarySearch(array1, 0, len(array1) - 1, value1) != -1:
    print("The element is found at ", BinarySearch(array1, 0, len(array1) - 1, value1))
else:
    print("The element is not present in the array")
if BinarySearch(array1, 0, len(array1) - 1, value2) != -1:
    print("The element is found at ", BinarySearch(array1, 0, len(array1) - 1, value2))
else:
    print("The element is not present in the array")

the output of which is

The element is found at  2
The element is not present in the array
Advantages
  • Takes less time to search
  • Efficiency is high
  • Does not scan each element instead utilizes a pinpoint searching mechanism
Disadvantages
  • Requires the array to be sorted
  • Requires more stack space and cache inefficient
  • It's error-prone and difficult to implement
  • Efficiently searching large datasets and arrays
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions