Coders Packet

Linear Vs Binary Search in Python

By Ankush Indulkar

This program is used to compare the time complexities of Linear Search and Binary Search.

Searching is one of the basic concepts of Data structures which is used to identify whether an element is present in the list of elements.

There are two basic methods to search an element:

a)Linear Search  b)Binary Search

 


a)Linear Search

In Linear Search, an array of numbers or lists is traversed from the starting position of the array till the end to find out whether the target element is present in the array of numbers or the list.

The Average Case time complexity and Worst-Case time complexity of Linear Search is O(n), where n is the number of elements.

The Best Case time complexity of Linear Search is O(1). This occurs when the target element is present at the first position.

It is efficient to use when the number of elements is less.

 


b)Binary Search

Binary Search is used in sorted arrays to find the position of the target element by finding the middle element of the array. The target element is then compared with the middle element and there are three cases:

i)If the target element is equal to the middle element then the element is found and returned.

ii)If the target element is less than the middle element then the element is searched on the left side of the middle element till it is found.

iii)If the target element is more than the middle element then the element is searched on the right side of the middle element till it is found.

The Best Case time complexity of the Binary Search is O(1) when the target element is equal to the middle element.

The Average Case time complexity and Worst-Case time complexity is O(log n), where n is the number of elements in the array.

It is efficient to use when the number of elements is more.


The time required to search an element in Binary search is less as compared to Linear Search.

The time module is used in the program to calculate the time taken for Linear Search and Binary Search separately.  

The random module is used to randomly create a list of elements in the program.

Download project

Reviews Report

Submitted by Ankush Indulkar (Ankush2308)

Download packets of source code on Coders Packet