查找算法之-二分查找

查找是针对已排序数进行查找的。
1、二分查找非递归实现
思想：通过while循环不断在新的区间中二分查找

public int binarySearch(int [] arr, int key){
  if(arr == null || arr.length == 0 || key < arr[0] || key > arr[arr.length-1]) {
    return -1;
  }
  int low = 0;
  int high = arr.lenght - 1;
  while(low <= high) {
    int middle = low + (high  -low >>> 1);
    if(key = arr[middle]) {
        return middle;
    }else if(key < arr[middle]) {
        hight = middle - 1;
    }else {
        low = middle + 1;
    }
  }
 return -1;
}

2、二分查找递归实现

   public int binarySearch(int[] arr, int key, int low, int high) {
        if (low < high || arr == null || arr.length == 0 || key < arr[0] || key > arr[arr.length - 1]) {
            return -1;
        }
        int middle = low + (high - low >>> 1);
        if (arr[middle] == key) {
            return middle;
        } else if (arr[middle] > key) {
            return binarySearch(arr, key, low, middle - 1);
        } else if (arr[middle] < key) {
            return binarySearch(arr, key, middle + 1, high);
        }
        return -1;
    }