Binary Search in Java does not terminate

Question

I have been trying to implement binary search in Java, the program does not increment left after it reaches 10. I could easily get the code for the same on the internet, but I want to figure out why my code is not working.

class Test {
  public static void main(String[] args) {
    int[] li = { 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
        30 };
    int target = 19;
    int left = 0, right = li.length;
    while (left < right) {
      int mid = (right - left) / 2;
      if (li[mid] == target) {
        System.out.println(mid);
        break;
      }
      else if (li[mid] < target) {
        System.out.println("li[mid] < target");
        left = mid + 1;
        System.out.println(left);
      }

      if (li[mid] > target) {
        System.out.println("li[mid] > target");
        right = mid - 1;
      }
    }
  }
}

The output

li[mid] < target
10
li[mid] < target
10
li[mid] < target
10
li[mid] < target
10
li[mid] < target
10

Answer 1

You've got the concept of Binary search correct, but there are some minor issues. First, right should be set to li.length-1. Then, when you assign mid, you need to add left as well. The code will now be:

    // ...
    int target = 19;
    int left = 0, right = li.length-1; // 1. fix value of right
    while (left < right) {
      int mid = left + (right - left) / 2; // 2. added left to mid
      if (li[mid] == target) {
        // ...

1. The array is zero indexed, and length returns the number of elements in the array. The elements themselves, go from 0 to length-1. So, right is adjusted to contain the index of the final element. You can test this out by removing the -1 and setting target to the last element 30. This will cause an error.

2. mid is supposed to store the index of the middle element of the currently searched section of the array. The current section starts at left and ends at right. So, to find the middle element, we use lower bound + (upper bound - lower bound) / 2.