CODEWITHSUNDEEP
javaalgorithm
Matt
Matt

Reputation: 501

Binary Search comparison

So I have some code which performs a binary search. Why is it essential for L and U to be compared with <=. Would I not get the same result with <?

  public static int bsearch(int t, List<Integer> A) {
    int L = 0, U = A.size() - 1;
    while (L <= U) { //******cant I just do: while(L<U) *****?
      int M = (L + U) / 2;
      if (A.get(M) < t) {
        L = M + 1;
      } else if (A.get(M) == t) {
        return M;
      } else {
        U = M - 1;
      }
    }
    return -1;
  }

Upvotes: 4

Views: 102

Answers (2)

Dave Cousineau
Dave Cousineau

Reputation: 13148

L and U may be better named L and R. They define the left and right extents of the unsearched section of the array. If your search narrows down to a single element, then they will be equal, but in order to test that last element, the while condition must hold or else you will skip it.

This is not only true in a list of one element. For example, searching the list { 1, 2, 3 } for the element 1. You will check 2, see that it's greater, reduce U to 0, and then will need to check element 0, which can only happen if you continue to check when L == U.

Upvotes: 2

Joe C
Joe C

Reputation: 15684

Here is an edge case where this would not work: a list of size 1.

In this case, we would have L == U == 0. Even if that one element happened to be the one for which you are looking, because the while condition is not satisfied with <, your element is never found.

Upvotes: 3

Related Questions