I'm always confused about the condition of the binary search algorithm and it costs me a lot of time in programming contests. My question is when to use each of these conditions?
1. while (low < high)
2. while (high - low > 1)
3. while (low <= high)
low
= the lowest value in the set of solutions.
high
= the largest value in the set of solutions.
Binary search condition
3k views Asked by Omar Abdelrahman At
1
while (low < high)
is used when you're searching the range[low, high)
. When updatinghigh
, usehigh = mid
. When updatinglow
, uselow = mid + 1
.while (high - low > 1)
is used when you're searching the range(low, high)
. When updatinghigh
, usehigh = mid
. When updatinglow
, uselow = mid
.while (low <= high)
is used when you're searching the range[low, high]
. When updatinghigh
, usehigh = mid - 1
. When updatinglow
, uselow = mid + 1
.Code below: