Sitemap

BINARY SEARCH PROBLEMS

4 min readJul 10, 2023

--

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)

visualization of Binary Search Algorithm

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:

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/binary-search-1587115620/1?page=1&sortBy=submissions
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 -1

1.1) check square number or not

Press enter or click to view image in full size

2) Find where is the index of extra element

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/index-of-an-extra-element/1?page=1&sortBy=submissions

3)

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/find-first-and-last-occurrence-of-x0849/1?page=1&sortBy=submissions
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,right

4) Ceil or Floor Number

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/search-insert-position-of-k-in-a-sorted-array/1?page=1&sortBy=submissions

5) common element [iterate elem from arr1 and check it is in arr2 and arr3 ] using binary search

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/common-elements1132/1?page=1&sortBy=submissions

5.1) peak index in mountain array

https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
Press enter or click to view image in full size
find position such that mid >mid+1 and mid-1
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

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/find-transition-point-1587115620/1?page=1&sortBy=submissions
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 -1

look 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

  1. 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
  2. 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)

Press enter or click to view image in full size
https://practice.geeksforgeeks.org/problems/0a7c7f1089932257071f9fa076f25d353f91e0fd/1

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 ans

similar problems

  1. https://leetcode.com/problems/koko-eating-bananas/
  2. https://youtu.be/9nUJ48EidUE
  3. https://leetcode.com/problems/split-array-largest-sum/

practice on:

https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/1/?sort_by=partially%20solved&p_level=

--

--

Shanjaikumar
Shanjaikumar

web designer | developer | maths ❤️ | memes