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

• Learn Singly Linked List
• Learn Doubly Linked List
• Create Hangman Game using Python
  
• Create Rock Paper Scissor Game using Tkinter