BINARY SEARCH PROBLEMS
This is an Fast Search Algorithm which searches an element by dividing the size of array and eliminating range which is not needed
CONDITIONS:
1) sorted array: Eighter in Ascending or Descending order
HOW IT WORKS:
1) A = [1,3,4,7,10,11,13,17,18] and Target = 17
2) low = 0 and high = length of A — 1
3) mid = ((low+high)//2)
In the first iteration a[mid] and target element is compared
if 10<17 then values <10 is waste so low range is updated to
low = mid+1
if a[mid] exceds target then higher range is updated to
high = mid -1
APPLICATIONS
syntax:
class Solution:
def binarysearch(self, a, n, k):
# code here
low = 0
high = len(arr)-1
while low<=high:
mid = ((low + high)//2)
if a[mid] < k:
low = mid + 1
elif a[mid] > k:
high = mid - 1
else:
return mid
return -11.1) check square number or not
2) Find where is the index of extra element
3)
class Solution:
def search(self,v,x,leftised):
i= -1
low = 0
high = len(v)-1
while low<=high:
mid = (low+high)//2
if v[mid]==x:
i = mid
if leftised:
high = mid-1
else:
low = mid+1
elif v[mid]<x:
low = mid+1
else:
high = mid -1
return i
def indexes(self, v, x):
# Your code goes here
left = self.search(v,x,True)
right = self.search(v,x,False)
return left,right4) Ceil or Floor Number
5) common element [iterate elem from arr1 and check it is in arr2 and arr3 ] using binary search
5.1) peak index in mountain array
class Solution:
def search(self,k,arr):
low = 0
high = len(arr)-1
while(low<=high):
mid = ((low+high)//2)
if arr[mid]<k:
low = mid+1
elif arr[mid]>k:
high = mid-1
else:
return True
else:
return False
def commonElements (self,A, B, C, n1, n2, n3):
# your code here
common_element = []
for elem in A:
if self.search(elem,B) and self.search(elem,C):
common_element.append(elem)
if len(common_element)>=2 and common_element[-1] ==common_element[-2]:
common_element.remove(common_element[-1])
if len(common_element)!=0 and all(elem==common_element[0] for elem in common_element):
return [common_element[0]]
else:
return common_element
6) Find Transitions point index from 0 to 1
def transitionPoint(arr, n):
#Code here
low = 0
high = n-1
if arr[0]==1:
return 0
elif arr==[0]:
return -1
while low <= high:
mid = (low+high)//2
if arr[mid]==1:
if arr[mid-1]==0:
return mid
else:
high = mid-1
else:
low = mid+1
return -1look for [1] in the array and compare if 0 is there before 1 [transition] , if it is not there first one [0111] then reduce the higher range
7) Find the missing number in sequence in log time
eg A = [5,7,9,11,15]
Get Shanjaikumar’s stories in your inbox
Join Medium for free to get updates from this writer.
use binary search to decide left/right side
- compare mid and 0th element and diff b/w both numbers as diffrence is constant so between 5 and 9 two elements are then so diff is 4
- in 15–9 diff should be 4 and not 6 so there is inbalance so sequence missing in right side
3) now compare mid and mid-1 or mid and mid+1 = diff
def seq():
a = [5,7,9,11,15]
low = 0
high = len(a)-1
diff = ((a[len(a)-1]-a[0] )/ len(a))
print(diff)
while low <= high:
mid = ((low+high)//2)
if mid+1<len(a) and a[mid+1]-a[mid]!=diff:
return a[mid+1]-diff
elif mid-1>=0 and a[mid]-a[mid-1]!=diff:
return a[mid-1]+diff
if a[mid]-a[0]!=(mid-0)*diff:
high = mid-1
else:
low = mid+1
return -1
print(seq())8) problems like finding optimal value(maximum(minimum) and minimum(maximum)
class Solution():
def possible(self,sweetness,mid,q):
sum = 0
c = []
for i in sweetness:
sum += i
if sum >= mid:
c.append(sum)
sum = 0
if len(c)>=q+1:
return True
return False
def maxSweetness(self, sweetness, n, k):
#your code goes here
low = min(sweetness)
high = sum(sweetness)
ans = 0
while low<=high:
mid = ((low+high)//2)
if self.possible(sweetness,mid,k):
ans = mid
low = mid+1
else:
high = mid-1
return anssimilar problems
- https://leetcode.com/problems/koko-eating-bananas/
- https://youtu.be/9nUJ48EidUE
- https://leetcode.com/problems/split-array-largest-sum/








