Binary Search Algorithm

Binary search algorithm which is also known as the logarithmic algorithm is an algorithm and it is used in finding an item from the sorted array. The binary search algorithm is faster than a linear search algorithm. Make sure you remember that the array must be sorted for the algorithm to work. You will understand why the array should be sorted as you go through the article.

A sorted array with 9 elements

Let us consider a sorted array of length N. Assume three indices one is the left index(L), one is the right index(R), and the middle index (M) is the floor value of (L+R)/2. For example, if L+R is 9, then the value of 9/2 is 4.5 and the floor value is 4.

Steps:

  1. Divide the algorithm into two chunks and the least index is the left index, the highest index is the right index R and the middle index is calculated by the above formula floor((L+R)/2).
  2. Check if the value of the array in mid-index (array[M]) is equal to the searched value. If the value is found, return the mid-index.
  3. Consider the item to search, if the item is higher than the value of the array in mid-index (array[M]), move the left index to the right of mid-index.
  4. Consider the item to search, if the item is lesser than the value of the array in mid-index (array[M]), move the right index to the left of mid-index.
  5. Do the steps from 1 to 4 recursively until you find search value is equal to (array[M]).
  6. In some cases, the value you search may not be found in the array. At that time, stop searching when the left-index L is greater than the right-index R (L > R).

To make it short there are only three cases that can occur when you search for an element in an array which is given below:

  • value = array[M]
  • value < array[M]
  • value > array[M]

Move the left and right pointer based on the situation you encounter and know when to stop (L > R).

Python Code for Binary Search Algorithm.

import math
def search(val, arr ):
n = len(arr)
l = 0
r = n-1
while l<=r:
m = math.floor((l+r)/2)
if val==arr[m]:
return m
elif val<arr[m]:
r = m-1
elif val>arr[m]:
l = m+1
return "not found"
print(search(4, [0, 1, 2, 3, 4]))

Complexity:

The worst case complexity of the linear search is O(n) because you have to search through the whole array when the element you search is at the end of an array. The worst case complexity of the binary search is O(log n) because the search space is reduced everytime when you search through the array.

Interesting Info: https://www.codementor.io/@ashwanitr001/is-your-binary-search-bug-free-16ptximygu

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

A SOLID Solution: Part II

Logging using Elastic Cloud for MuleSoft using HTTP Appender

Using Pandas’ .loc and .isin() to Filter for a List of Values in Python

Introduction to AJAX

QUICK SORT IN JAVASCRIPT

Quick Sort

How to perform CRUD operations using Blazor Server App Part-IX

How pair programming helped me to deal with Imposter Syndrome

A cup of coffee next to a laptop displaying a zoom call with many people.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abinaya Rajesh

Abinaya Rajesh

More from Medium

Data Structure and Algorithms: Complexity

Append nums to itself to get rid of circular effect.

Data Structures questions you might get asked on your interview

[LeetCode][C++] #26. Remove Duplicates from Sorted Array