Python binary search and linear search

In this python tutorial, you will learn about binary search and linear search in python with examples. Here we will check:

• What is binary search in python?
• Binary search in python without recursion
• Python recursive binary search
• Python binary search using a library find the first occurrence of an element
• Python binary search using a library find the greatest value smaller than n
• Linear search in python
• Linear search in python using list
• Linear search vs Binary search in python

What is binary search in python?

• A binary search is an algorithm that is used to find the position of an element in an ordered array.
• There are two ways to perform a binary search. In both approaches, we have the highest and lowest position in an array.
• The first approach is the iterative method and the second approach is the recursive method.
• A binary search is an efficient way of searching through a list of numbers, it is more efficient than a linear search because it cuts down the search to half.

Binary search in python without recursion

In a Python binary search, we will give a sorted list and we will find the element by using the binary search. In an iterative method, we will loop through every item in our list, find the middle value, and continue to do till the search complete.

Example:

def binary_searchiter(arr, n):
    low = 0
    high = len(arr) - 1
    mid = 0
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < n:
            low = mid + 1
        elif arr[mid] > n:
            high = mid - 1
        else: 
            return mid
    return -1
arr = [4, 7, 9, 16, 20, 25]
n = 7
r = binary_searchiter(arr, n)
if r != -1:
    print("Element found at index", str(r))
else: 
    print("Element is not present in array")

After writing the above code (binary search in python without recursion), Ones you will print then the output will appear as an “Element found at index 1”. Here, the iterative method is used to find the number on the list.

You can refer to the below screenshot for binary search in python without recursion

Python recursive binary search

We can also use recursion for binary search in Python. In recursive binary search, we will define a function, which keeps calling itself until the condition is met. We will first calculate the middle number and continue to do it till the search complete.

Example:

def binary_search(arr, low, high, number):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == number:
           return mid
        elif arr[mid] > number:
           return binary_search(arr, low, mid-1, number)
        else:
           return binary_search(arr, mid+1, high, number)
    else:
        return -1
arr = [5, 12, 17, 19, 22, 30]
number = 22
r = binary_search(arr, 0, len(arr)-1, number)
if r != -1:
    print("Element found at index", str(r))
else:
    print("Element is not present in array") 

After writing the above code (python recursive binary search), Ones you will print then the output will appear as an “ Element found at index 4 ”. Here, the recursive method is used and we are passing two new parameters to our binary_search function.

You can refer to the below screenshot for python recursive binary search.

Python binary search using a library find the first occurrence of an element

In this we will use the library function to do a binary search, we need to import “from bisect import bisect_left” and bisect.bisect_left(a, n) function is used to return the leftmost insertion point of n in a sorted list.

Example:

from  bisect import bisect_left
def Binary_Search(a, n):
    i = bisect_left(a, n)
    if i != len(a) and a[i] == n:
        return i
    else:
        return -1
a = [2, 5, 5, 6, 10]
n = int(5)
val = Binary_Search(a, n)
if val == -1:
    print(n, "is not present")
else:
    print("First occurence of", n, "is present at", val)

After writing the above code (python binary search using a library find the first occurrence of an element), Once you will print then the output will appear as “First occurrence of 5 is present at 1”. Here, by using the bisect_left() function it will return the first occurrence of the element present in the list.

You can refer to the below screenshot find the first occurrence of an element

Python binary search using a library find the greatest value smaller than n

We can get the greater value, smaller than n by using the bisect_left().

Example:

from bisect import bisect_left
def Binary_search(a, n):
   i = bisect_left(a, n)
   if i :
      return i-1
   else:
      return -1
a = [2, 4, 6, 8, 10, 12]
n = int(10)
val = Binary_search(a, n)
if val == -1:
   print(n, "is not present")
else:
   print("Larger value, smaller than", n, "is at position", val)

After writing the above code (python binary search using a library find the greatest value smaller than n), Once you will print then the output will appear as “Larger value, smaller than 10 is at position 3”. Here, by using the bisect_left() function it will return the larger value smaller than n.

You can refer to the below screenshot find the greatest value smaller than n

Linear search in python

Python Linear search is the most basic kind of searching algorithm. A linear or sequential search is done when you search the item in a list one by one from start to end to find the match for what you are searching for.

Example:

def linear_search(arr, n):
   for i in range(len(arr)):
      if arr[i] == n:
         return i
   return -1
arr = [3, 2, 6, 19, 15, 20]
n = 15
r = linear_search(arr, n)
if(r == -1):
    print("Element not found")
else: 
    print("Element found at index",str(r))

After writing the above code (linear search in python), Ones you will print then the output will appear as an “ Element found at index 4 ”. Here, a linear search is used to search the element in the list in sequential order and if we find the element then, it will return the index of that particular element.

You can refer to the below screenshot for linear search in python.

Linear search in python using list

To perform a linear search on a list in Python, we have to start from the leftmost element of the list and then it will compare with each element in the list, and if the element matches then it will give the position else it will return not found.

Example:

pos = -1
def linear_search(list,number):
    for i in range(len(list)):
        if list[i] == number:
            globals() ['pos'] = i
            return True
    return False
list = ['Welcome', 2, 'Python', 5]
number = 5
if linear_search(list, number):
    print("Found the element",pos)
else:
    print("Not Found")

After writing the above code (linear search in python using list), Once you will print then the output will appear as “Found the element at index 3”. Here, a linear search using a list is used to search the element in the list in sequential order and if we find the element then, it will return the index of that particular element.

You can refer to the below screenshot for linear search in python using list

Linear search vs Binary search in python

Linear search	Binary search
Linear search is iterative in nature and uses a sequential approach.	Binary search implements divide and conquer approach.
The best-case time in linear search is for the first element i.e, O(1).	In a binary search, the best-case is for the middle element i.e, O(1)
The time complexity of a linear search is O(N).	Time complexity for binary search is O(log N).
Linear search is easy to use.	Binary search is tricky.
In a linear search, there is no need for any order.	In a binary search, it is necessary to be arranged in order.

You may like the following Python tutorials:

• Python convert list to string
• Check if a list is empty in Python
• Python TypeError: ‘list’ object is not callable
• Python convert tuple to list
• Python dot product and cross product
• Python exit command (quit(), exit(), sys.exit())
• Python input and raw_input function
• Python read a binary file

In this tutorial, we learned about binary search and linear search in Python and also we have seen how to use it with an example like:

• What is binary search in python?
• Binary search in python without recursion
• Python recursive binary search
• Python binary search using a library find the first occurrence of an element
• Python binary search using a library find the greatest value smaller than n
• Linear search in python
• Linear search in python using list
• Linear search vs Binary search in python