改進的二分查找

import java.util.Comparator;

public class MyUtil {

   public static <T extends Comparable<T>> int binarySearch(T[] x, T key) {
      return binarySearch(x, 0, x.length- 1, key);
   }

   // 使用循環實現的二分查找
   public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) {
      int low = 0;
      int high = x.length - 1;
      while (low <= high) {
          int mid = (low + high) >>> 1;
          int cmp = comp.compare(x[mid], key);
          if (cmp < 0) {
            low= mid + 1;
          }
          else if (cmp > 0) {
            high= mid - 1;
          }
          else {
            return mid;
          }
      }
      return -1;
   }

   // 使用遞歸實現的二分查找
   private static<T extends Comparable<T>> int binarySearch(T[] x, int low, int high, T key) {
      if(low <= high) {
        int mid = low + ((high -low) >> 1);
        if(key.compareTo(x[mid])== 0) {
           return mid;
        }
        else if(key.compareTo(x[mid])< 0) {
           return binarySearch(x,low, mid - 1, key);
        }
        else {
           return binarySearch(x,mid + 1, high, key);
        }
      }
      return -1;
   }
}

上面的代碼中給出了折半查找的兩個版本，一個用遞歸實現，一個用循環實現。需要注意的是計算中間位置時不應該使用(high+ low) / 2的方式，因為加法運算可能導致整數越界，這里應該使用以下三種方式之一：low + (high - low) / 2或low + (high – low) >> 1或(low + high) >>> 1（>>>是邏輯右移，是不帶符號位的右移）

轉自：https://blog.csdn.net/jackfrued/article/details/44921941