← Back to Data Structures and Algorithms in Python

In this article, we will write a Python program for Linear Search and Binary Search.

What is Linear Search?

Linear search is also known as a sequential searching algorithm to find the element within the collection of data. The algorithm begins from the first element of the list and starts checking every element until the expected element is found. If the element is not found in the list, the algorithm traverses the whole list and returns “element not found”. Therefore, it is just a simple searching algorithm.

Python Program for Linear Search

def LinearSearch(array, n, k):

    for j in range(0, n):

        if (array[j] == k):

            return j

    return -1

 
array = [10, 30, 50, 70, 90]

k = 30

n = len(array)

result = LinearSearch(array, n, k)

if(result == -1):

    print("Element not found")

else:

    print("Element found at index: ", result)

Output:

Element found at index:  1

What is Binary Search?

Binary search is used with a similar concept, i.e to find the element from the list of elements. Binary search algorithms are fast and effective in comparison to linear search algorithms. The most important thing to note about binary search is that it works only on sorted lists of elements. If the list is not sorted, then the algorithm first sorts the elements using the sorting algorithm and then runs the binary search function to find the desired output.

Python Program for Binary Search (Iterative Method)

def binarySearch(arr, k, low, high):

   
    while low <= high:
        mid = low + (high - low)//2
        if arr[mid] == k:
            return mid
        elif arr[mid] < k:

            low = mid + 1
        else:

            high = mid - 1
    return -1

arr = [10, 30, 50, 70, 90]

k = 50
result = binarySearch(arr, k, 0, len(arr)-1)

if result != -1:

    print("Element is present at index " + str(result))

else:

    print("Not found")

Output:

Element is present at index 2

Python Program for Binary Search (Recursive Method)

def BinarySearch(arr, k, low, high):

    if high >= low:

        mid = low + (high - low)//2

        if arr[mid] == k:
            return mid

        elif arr[mid] > k:
            return BinarySearch(arr, k, low, mid-1)

        else:
            return BinarySearch(arr, k, mid + 1, high)

    else:
        return -1


arr = [10, 30, 50, 70, 90]
k = 50

result = BinarySearch(arr, k, 0, len(arr)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Output: