AP计算机教程11-3：折半查找

折半查找仅在数据已被排好序时可以使用。

算法比较目标值和中间索引取到的元素值。如果没有命中，则目标值（如果找到的话）必然在当前元素的左侧或右侧。这样可以继续重复这个过程，查找左侧或右侧的中间元素值，每轮循环必然将查找区域缩减一半。

算法使用(left + right) / 2来计算中间索引值，最初的left为0而right为array.length - 1。记住整数除法会舍掉小数部分，因而5 / 2的结果是2。如果中间索引取到的元素值正是待查找值，则查找结束并返回中间索引。如果待查找值比中间索引的元素值小，right会被设为middle - 1，然后在左侧区域重复查找过程。如果待查找值比中间索引的元素值小，left会被设为middle + 1，然后在右侧区域重复查找过程。当区域左边界大于右边界时，查找也结束，返回表示未找到的-1。以下是一个AP计算机折半查找的示例代码。

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);
   }
}

Which will cause the shortest execution of a binary search looking for a value in an array of integers?

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.

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)?