This book is now obsolete Please use CSAwesome instead.

13.3. Binary Search

A binary search can only be used if the data is sorted.

It compares a target value to the value in the middle of a range of indices. If the value isn’t found it looks again in either the left or right half of the current range. Each time through the loop it eliminates half the values in the search area until either the value is found or there is no more data to look at. Click on this Binary Search Animation to see how it works.

Binary search calculates the middle index as left + right / 2 where left starts out at 0 and right starts out at the array length - 1 (the index of the last element). Remember that integer division gives an integer result so 2.5 becomes 2. 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.

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 middle int index = binarySearch(arr1,15); System.out.println(index); // test when the target is the first item in the array index = binarySearch(arr1,-20); System.out.println(index); // test when the target is in the array - last index = binarySearch(arr1,432); 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 the following link: BinarySearch Ex

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

• The value is the first one in the array
• This would be true for sequential search, not binary.
• The value is in the middle of the array
• If the value is in the middle of the array the binary search will return after one iteration of the loop.
• The value is the last one in the array
• How would that be the shortest in a binary search?
• The value isn't in the array
• This is true for the longest execution time, but we are looking for the shortest.

13-3-3: Which of the following conditions 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.

• I only
• You can use a binary search on any type of data that can be compared, but the data must be in order.
• I and II
• You can use a binary search on any type of data that can be compared.
• II only
• The only requirement for using a Binary Search is that the values must be ordered.
• II and III
• The array can contain duplicate values.

13-3-4: 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)?

• 2
• It will first compare with the value at index 2 and then index 4 and then return 4.
• 1
• This would be true if we were looking for 23.
• 3
• This would be true if we were looking for 31.

You have attempted of activities on this page