How to type a BinarySearch method while-loop without break statement?

user_11671900 0
Viewed 375

I just finished studying the simple BinarySearch algorithm, but one thing that bugs me is that I was taught that break (and continue) statements are often redundant in Java and you can do with most while-loops without them. But I can't figure out how to get rid of hem from the BinarySearch while-loop below:-

public static void BinarySearch(int[] list, int key){
int lo = 0;
int hi = list.length-1;
int mid = 0;
while(lo<=hi){
    mid = lo + (hi-lo) / 2;
    if(key<list[mid])
        hi = mid-1;
    else if(key>list[mid])
        lo = mid+1;
    else {
        System.out.println("Key is found at index = " + mid);
        break;
    }
    if(lo>hi){
        System.out.println("Key doesn't exist in the list");
    }
}

Question 1: Why does the loop keeps going on and on if I didn't include the break statement? Shouldn't the variable "lo" eventually become greater than "hi"? How come the last if- conditional can see that, but not the while-loop-conditional?

Question 2: How can I can type the while-loop without needing the break statement?

infinite break while-loop java
1 Answers

The basic strategy is to add extra conditions to the loop, and set and use these conditions in the code within the loop.

For example, for the above loop:

int keyIndex = -1;

. . .

while ( (lo<=hi) && (keyIndex == -1) ) {
    . . .
    else {
        System.out.println("Key is found at index = " + mid);
        keyIndex = mid;     // <<< 
    }
    . . .
}

However, using a break statement for loops such as this is considered an acceptable programming practice by many developers.

Here is a reddit discussion on the use of break and continue.

And here is a question in the sister site on software engineering.

As to why your loop does not exit without the break statement is if the key is found, the value of lo is not changed. So no, the value of lo does not necessarily become greater than high.

user_2249350
Related