Ref: https://en.wikipedia.org/wiki/Binary_search_algorithm
function binary_search_leftmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] < T:
L := m + 1
else:
R := m
return L
Wikipedia provided this function for finding the leftmost occurrence of an element and this magically (at least for me :P) denotes the number of elements less than the target given (whether the target is in the array or not)
For example, consider an array [1, 2, 4, 4, 4, 4, 4, 7, 9, 16] of the size 10.
wiki_leftmost(lst, 0) == 0
0 is not in the array.
The answer 0 represents the elements < 0 which is 0.
wiki_leftmost(lst, 1) == 0
1 is in the array. The answer 0 represent in the index of the leftmost occurence of 1.
The answer also represents the elements < 1 which is 1.
wiki_leftmost(lst, 4) == 2
4 is in the array. The answer 2 represent in the index of the leftmost occurence of 4.
The answer also represents the elements < 4 which is 2.
wiki_leftmost(lst, 7) == 7
7 is in the array. The answer 7 represent in the index of the leftmost occurence of 4.
The answer also represents the elements < 7 which is 7.
wiki_leftmost(lst, 10) == 9
10 is not in the array.
The answer 9 represents the elements < 10 which is 9.
wiki_leftmost(lst, 16) == 9
16 is in the array. The answer 9 represent in the index of the leftmost occurence of 16.
The answer also represents the elements < 16 which is 9.
wiki_leftmost(lst, 200) == 10
20 is not in the array.
The answer 10 represents the elements < 200 which is 10.
I understood the intuition behind the normal binary search (which is pretty simple) and also its alternative version (the one without the equality condition) (both are present in the wiki page). But I am not quite able to understand the intuition behind this algorithm. I took examples and did go through the flow, but I needed a proper intuition to visualize and understand more of the algorithm.
PS: There are a few similar questions, but none of them was mentioned with all these details and the answers were not something that I am ok with.
Goal: Find the leftmost such that A[L] == T and L is minimum.
We remodel our goal to check for equality since the original binary search may give an element somewhere in middle of multiple dupes, instead we say if we can find index of last element which was less than T, our answer could possibly be the next element after it if it exists. See the comments in psuedocode.
function binary_search_leftmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2) # partition in 2 parts get middle
if A[m] < T: # last element seen so far which is less than T
L := m + 1 # this could possibly be A[L] == T, if not keep searching towards right
else:
R := m # A[m] >= T, mth element could be our answer
return L # after this we still need to check if L < n and A[L] == T
Similarly, for rightmost match we remodel to look for rightmost element which was greater than T, our target element could be just before this last rightmost element. See the comments in psuedocode.
function binary_search_rightmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2) # partition in 2 parts get middle
if A[m] > T: # last element seen so far which is greater than T
R := m # our answer lies between [L, m], since we are interested in A[m] > T and it is possible A[m] is the only greater element than T
else:
L := m + 1 # since A[m] <= T and we are only interested in A[i] > T
return R - 1 # return previous element, still need to check if R-1 >= 0 and A[R-1] == T