折半查找(带泛型参数)

优化：

package org.mobiletrain;

import java.util.Comparator;

//Collections工具类
public class Test01 {
    
    //折半查找
    public static <T extends Comparable<T>> int binarySearch(T[] array,T key){
        int start = 0;
        int end = array.length - 1;
        while(start <= end){
            int mid = (end - start) / 2 + start;
            if (array[mid].equals(key)) {
                return mid;
            }
            else if (array[mid].compareTo(key) > 0) {
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        return -1;
    }
    
    public static <T> int binarySearch(T[] array,T key,Comparator<T> comp){
        int start = 0;
        int end = array.length - 1;
        while(start <= end){
             //int mid = (start + end) / 2; //有溢出的风险
            int mid = (end - start) / 2 + start;
            // int mid = (start + end) >>> 1; //逻辑右移（不带符号位的右移）
            if (array[mid].equals(key)) {
                return mid;
            }
            else if (comp.compare(array[mid],key) > 0) {
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        return -1;
    }

}

更优化：

class Hello {

  public static <T extends Comparable<T>> int binarySearch(T[] array, T key) {
    return _binarySearch(array, key, 0, array.length - 1);
  }
  
  private static <T extends Comparable<T>> int _binarySearch(T[] array, T key, int start, int end) {
    if (start <= end) {
      int mid = (start + end) >>> 1;
      if (key.compareTo(array[mid]) < 0) {
        return _binarySearch(array, key, start, mid - 1);
      } else if (key.compareTo(array[mid]) > 0) {
        return _binarySearch(array, key, mid + 1, end);
      } else {
        return mid;
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    String[] x = { "apple", "banana", "grape", "pitaya", "watermelon" };
    System.out.println(binarySearch(x, "grape"));
    System.out.println(binarySearch(x, "orange"));
    System.out.println(binarySearch(x, "apple"));
  }
}