binary search without equals case
275

To do a binary search without the equals case you need to respect the following rules:

you either do:

if f(mid) < target:
	l = mid + 1 
else:
	r = mid
	# in this case, mid is (l + r) // 2 ( small type of mid )

or

if f(mid) <= target:
	l = mid
else:
	r = mid - 1
	# in this case mid = ( l + r + 1 ) // 2 ( big type of mid )

First think about the cases forgetting where the equal sign goes and then, to know where does the = part go, just look at where the mid is ( not mid + 1 or mid - 1 ).

Some exercises allow you to do type 1, and type 2. But some exercises might only let you use one type. The tricky thing is to identify which type.
For example in the exercise: https://leetcode.com/problems/search-a-2d-matrix/
if you cut the lines based on the first element, you will only can discriminate between,
[0 ... mid - 1] and [mid, ... n]. Because if mid is too small, you don't know if the target will be in the mid line or in the line above and after..

Comments (0)