Binary Search: Why and How

In DynamicArray the elements sit in whatever order they were added, so comparing the target against any one element tells you nothing about where the rest are. In sorted data, comparing the target against the middle element tells you which side the target must be on, and everything on the other side is ruled out in that one comparison. So a sorted array lets you halve the range on every step, instead of checking one element at a time.

public static int binarySearch(int[] arr, int target) {
  int low = 0;
  int high = arr.length - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    int cmp = Integer.compare(arr[mid], target);
    if (cmp == 0) {
      return mid;
    } else if (cmp < 0) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

Step 1: low=0, high=6, mid=3.

   0    1    2    3    4    5    6
┌────┬────┬────┬────┬────┬────┬────┐
│  2 │  5 │ 11 │ 18 │ 24 │ 31 │ 40 │
└────┴────┴────┴────┴────┴────┴────┘
   ↑              ↑              ↑
  low            mid           high

arr[3]=18 is less than 31, so set low = mid + 1 = 4.

Step 2: low=4, high=6, mid=5.

   0    1    2    3    4    5    6
┌────┬────┬────┬────┬────┬────┬────┐
│░ 2░│░ 5░│░11░│░18░│ 24 │ 31 │ 40 │
└────┴────┴────┴────┴────┴────┴────┘
                       ↑    ↑    ↑
                      low  mid high

arr[5]=31 equals the target. Return 5.