BINARY SEARCH ALGORITHM

AUTHOR – Thota Ashavanthini Krishna

One of the most popular algorithms known as binary search algorithm. In computer science, binary search, also called half-interval search is a search technique that locates a target value's position inside a sorted array. There are various applications of binary search algorithm. There are numerous algorithmic tasks that involve a binary search in order to achieve a model solution. They show up in technical interview questions, coding tests, examinations, and code challenges. In this paper, we will study the implementation of binary search in python.

---

INTRODUCTION

There is a huge amount of data readily accessible in the modern world. Searching algorithms are so crucial to find our desired items or elements with specific properties from the data set. As a result, it has become the fundamental process in the data processing. There are various methods that are used in the search process. The most important methods are the

• Linear/sequential search method,

• Binary search method,

• Direct search method,

• Interpolation search method,

• Hash search method.

The linear search method is most widely used among the five existing methods. But in the linear search method, if the item we are looking for is not available in the data set, then it will continue searching until the last element. Therefore, the linear search method is inadequate when implemented in large data sets. Hence, the Binary Search method is implemented to address the issue. The divide and conquer rule is the main advantage of the binary search method over the linear search method.

The linear search method involves searching every element of the data set in a single direction. In contrast, the binary search method divides the data set into two halves and performs the search in both directions. As a result, the binary search approach outperforms other search methods.

CONCEPT OF BINARY SEARCH

The binary search algorithm is a technique used to search an element from a sorted list. It is necessary for a list to be sorted to check an element in it. It cannot be implemented on the list which is not sorted. Sorted in the sense, the elements in the list should be arranged in ascending order. This process of searching involves dividing the list into two parts and calculating its middle element.

The target element will be compared with the middle element of the list.

• If it gets matched, then it returns the location of the middle element.

• If the target element is less than the middle element, then we would search it in the first half of the array that locates left to the middle element.

• If the target element is greater than the middle element, then we would search it in the second half of the array that locates right to the middle element.

• But if the target element does not match with the elements present in the list, then it will return the statement, “Element not found”.

PROCEDURE

Let us consider an array that consists of 11 terms with their locations from 0 to 10.

Let us try to search element 69.

Our target value is 69.

FIG:1

In this array

• 2 is the first value.

• 92 is the last value.

Middle term =  First + Last / 2 =  (0 + 10) / 2 = 5th term

FIG:2

• Hence, 42 is the middle value.

• Since 42 is less than 69, the target element must be on the right-hand side of the middle term.

• Now, we change our first term to middle term + 1 and find the new mid-value again.

FIG:3

First term = mid +1 = 5 + 1 = 6th term Last term = 10th term Middle term = First + Last / 2 = (6 + 10) /2 = 8th term.

FIG:4

• Hence the new middle value will be 78.

• It does not match our target element again. This time, it is more than our target value. It means the target element must be on the left-hand side of the middle term.

• We will calculate the middle term again.

• Now, we change our last term to middle term - 1 and find the new mid-value again.

FIG:5

First-term = 6th term

Last term = mid - 1 = 10 - 1 = 9th term

Middle term = First + Last / 2 = (6 + 9)/2 = 7.5 (Consider its integer value) = 7th term

FIG:6

• Hence the new middle value will be 69.

• This matches our target value.

• Hence, the location of 69 is 7.

CODE IMPLEMENTATION

Let us implement the algorithm in python

Step – 1:

We need to define the built-in function binary Search which is used for this algorithm. Let the first term be the variable “first”, and the last term be the variable “last”. This function returns the index of the target item if it is found in the data set, else returns -1.

def binarySearch(arr, first, last, item):

Step – 2:

Check the base case whether the last item is greater than the first item or not. This means our list is sorted. Now we can find the mid-value using its formula.

if last >= first: 
  mid = int((first+last)/2)

Step – 3:

Now, if the target element is present at the middle itself, then it will return the location of the middle term.

if arr[mid] == item : 
 return mid

Step – 4:

If it is not present in the middle, then check whether the target item is smaller than the mid-value or greater than the mid-value. If it is greater than the mid-value, then it can be present in the right subarray. Hence, the value of the first term becomes mid + 1.

 elif arr[mid] < item : 
 return binarySearch(arr,mid+1,last,item) 

Step – 5:

If it is not present in the right subarray, then it must be smaller than the mid-value. Hence it can be present in the left subarray. This time, the value of the last term becomes mid - 1.

else: 
 return binarySearch(arr,first,mid-1,item) 

Step – 6:

If it is not even present in the left subarray, then the element is not present in the array. As a result, it will return - 1.

 return -1 

Step – 7:

Here comes the driver code, we will mention our array. Then it will ask the item we want to search for. If the output does not return -1, it will print the target element location else it will print the statement "Item not found".

arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];  
item = int(input("Enter the item which you want to search ?"))  
location = -1;   
location = binarySearch(arr,0,9,item);  
if location != -1:   
 print("Item found at location %d" %(location))  
else:   
 print("Item not found")
 

So yes, we have implemented the binary search algorithm in python successfully.

There are various applications of Binary Search. They can be used to solve a broader range of problems, such as locating the next lowest or largest element in an array relative to the target, even if the target is not present in the array. Except in small arrays, binary search is faster than linear search. However, hash tables, for example, are advanced data structures built for quick searching and can be searched more efficiently than binary search. Binary search includes a variety of methods.

Fractional cascading, in particular, accelerates binary searches across several arrays for the same value. In computational geometry and a lot of other domains, fractional cascading efficiently handles a variety of search issues. Binary search is extended to unbounded lists via exponential search. Binary search is also used to create the binary search tree and the B-tree data structures.

GitHub Code:

• https://github.com/Ashvanthini9/Binary-Search-Algorithm

References :

1. http://www.btechsmartclass.com/data_structures/binary-search.html

2. https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

3. Binary search algorithm, WikiJournal of Science, 2019.

4. Modified Binary Search Algorithm, International Journal of Applied Information Systems, Foundation of Computer Science FCS, Volume 7– No. 2.

5. Digital Dictionary Using Binary Search Algorithm, The International Conference on Computer Science and Applied Mathematics.