二分查找

递归和非递归实现

public class BinarySearch {

  public static void main(String[] args) {
    int[] arr = {1, 8, 10, 89, 1000, 1234};
    System.out.println(search(arr, 0, arr.length-1, 1000));
  }

  // 递归
  static int search(int[] arr, int left, int right, int searchedValue) {
    int mid = (left+right)/2;
    if(right< left) {
      return -1;
    }
    if(arr[mid] == searchedValue) {
      return mid;
    }
    if(searchedValue > arr[mid]) {
      return search(arr, mid + 1, right, searchedValue);
    } else {
      return search(arr, left,mid - 1, searchedValue);
    }
  }

 // 二分查找非递归实现
  static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right){
      int mid = (left + right) / 2;
      if(arr[mid] == target){
        return mid;
      } else if(arr[mid] > target) {
        right = mid -1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
}