educative.io

What Is Binary Search? - Binary Search for Coding Interviews

Courses
,
#1

Is there a benefit of writing this binary algo with the line “while low + 1 <= high” instead of while low <= high and in the division adding +1 or -1 to the low or high? I ask because I find it harder to remember to add 1 to the while and to also check for the left after the while loop breaks. Below is the code that I am referring to instead of the example. I just want to know if I am missing some benefit. Thanks.

    high = x
    low = 0
    
    while low <= high: 
        mid = (low + high)//2
        mid_sqr = mid * mid 
        
        if mid_sqr <= x:
            low = mid + 1
        else:
            high = mid -1
    return low -1
#2

Hey Chey_Yeary,
The code you have entered has a lot of issues, for a good code you must refer to the Lesson, but your question regarding why we are using low + 1 <= high in the while loop. Let’s start with a simple Example
[1,2,4,7,8,9,12,14,16,19]
Suppose this is the list and we wanted to search number 25 from the list, which is not available in the list, so the order of {iteration, mid, low, high} will be like this
{ 1 , 5 , 0 , 10 }
{ 2 , 8 , 6 , 10 }
{ 3 , 9 , 9 , 10 }
{ 4 , 10 , 10 , 10 }
So at this point the code will try to access the element at index 10 which will exceed the limit of list and it will raise an exception of List Index Out of range.
So it is compulsory to manage these things as well, please refer to the lesson that is well explained and still if you have any question, you can ask