Binary search calculates the middle index as the `left + right / 2` where left starts out at 0 and right starts out at the array length - 1 (the index of the last element). It compares the value at the middle index with the target value (the value you are searching for). If the target value is less than the value at the middle it sets right to middle minus one. If the target value is greater than the value at the middle it sets left to middle plus one. Otherwise the values match and it returns the middle index. It also stops when left is greater than right which indicates that the value wasn’t found and it returns -1.

The code for `binarySearch` below is from the AP CS A course description.

1 2 3 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 31 32 33 34 35 36 | ```
public class SearchTest
{
public static int binarySearch(int[] elements, int target) {
int left = 0;
int right = elements.length β 1;
while (left <= right)
{
int middle = (left + right) / 2;
if (target < elements[middle])
{
right = middle β 1;
}
else if (target > elements[middle])
{
left = middle + 1;
}
else {
return middle;
}
}
return β1;
}
public static void main(String[] args)
{
int[] arr1 = {-20, 3, 15, 81, 432};
// test when the target is in the array
int index = binarySearch(arr1,-20);
System.out.println(index);
// test when the target is not in the array
index = binarySearch(arr1,53);
System.out.println(index);
}
}
``` |

To see this executing using the Java Visualizer click on this link

12-3-1: Which will cause the *shortest* execution of a binary search looking for a value in an array of integers?

12-3-2: Which of the following condition must be true in order to search for a value using binary search?

```
I. The values in the array must be integers.
II. The values in the array must be in sorted order.
III. The array must not contain duplicate values.
```

12-3-3: How many times would the while loop execute if you first do int[] arr = {2, 10, 23, 31, 55, 86} and then call binarySearch(arr,55)?