Skip to main content

Binary Search

 Binary search is a efficient way to find element from sorted array, It works on decrease and conquer method.......

How it works?

Binary search compares the target value to the middle element of the array, if target value is not equal to middle element it check whether middle element is greater than or less than target value, if middle element is greater than target value then target value can not be in right part of the array now once again this process repeats for left side of array until target value equals to middle element.



Steps:

  1. Compare target value = x and middle element = m 
  2. if x=m then return 
  3. else, according to m>x or m<x repeat step 1 and 2 for remaining part.
 

Code:

  • Recursive Method:
def binarySearchRecursive(targetValue,arr,min,max):
if min>max:
return -1
else:
mid = (min + max)//2
if arr[mid] > targetValue:
return binarySearchRecursive(targetValue,arr,min, mid-1)
elif arr[mid] < targetValue:
return binarySearchRecursive(targetValue,arr,mid+1,max)
else:
return mid

arr = [1,2,4,5,22,23,26,27,32,62,72,75,85,97,113,134,145]
print(binarySearchRecursive(72,arr,0,len(arr))) # index no: 10
 
  •  Iterative Method:
def binarySearch(targetValue, arr):
min = 0
max = len(arr)-1
guess = None
totalNumberOfGuesses = 0
while max>min:
guess = (min + max)//2
if arr[guess] == targetValue:
totalNumberOfGuesses += 1
print(f"total number of guesses : {totalNumberOfGuesses}")
return guess
elif arr[guess] > targetValue:
totalNumberOfGuesses += 1
max = guess - 1
else:
totalNumberOfGuesses += 1
min = guess + 1
return -1

arr = [1,2,4,5,22,23,26,27,32,62,72,75,85,97,113,134,145]
targetValue = 72
print(f"Index of {targetValue} is ",binarySearch(targetValue,arr))
#output:
# total number of guesses : 3
# Index of 72 is 10
 

Time Complexity:
  • Best:𝛺(1)
  • Average:Θ(log n)
  • Worst:O(log n)
Space Complexity: O(1)

What if we've use Linear Search Here?

For, arr = [1,2,4,5,22,23,26,27,32,62,72,75,85,97,113,134,145]
Target Value = 72
Linear Search will take 11 steps
Time complexity O(n)

Note: If you've any question or suggestion you can right down in comment section
Reference: Wikipedia

Thank You 😊😊

Some Other useful Posts


Comments

Popular posts from this blog

Products Which I like

headphone Buy now Camera Buy now

What is Docker?

 Hello Everyone , Today we'll talk about what is docker ?, how to use it ? and why you should use it ?, then let's begin...

What is Digital Root ?

 What is a Digital root? if you have done little competitive programming or practice for Data Structure or anything else you have got a problem where you need to sum all digits of the number and do this process until the number becomes a single-digit number. so that is Digital Root, let's talk about it.