class BinarySearch {
  
  // 二分查找非遞歸方式
  // arr 給定已排序數(shù)組
  // num 要查找的數(shù)
  public static int search(int[] arr, int num) {
    int low = 0;
    int high = arr.length - 1;
    int mid = 0;
    while (low <= high) {
      mid = (low + high) / 2;
      if (num < arr[mid]) {
        high = mid - 1;
      }
      
      if (num > arr[mid]) {
        low = mid + 1;
      }
      if (num == arr[mid]) {
        return mid;
      }
    }
    return -1;  // 沒找到
  }
  
  
  // 二分查找遞歸方式
  // arr 給定已排序數(shù)組
  // num 要查找的數(shù)
  // low 初始左側(cè)指針 指向第一個元素
  // high 初始末尾指針 指向最后一個元素
  public static int binarySearch(int[] arr, int num, int low, int high) {
    
    int mid = (low + high) / 2; 
    
    // 遞歸結(jié)束條件
    if (low > high) {
      return -1;
    }
    
    if (num < arr[mid]) {
      return binarySearch(arr, num, low, mid - 1);
    } else if (num == arr[mid]) {
      return mid;
    } else {
      return binarySearch(arr, num, mid + 1, high);
    }
    
  }
  
  
  public static void main(String[] args) {
    
    // 給定數(shù)組 從小到大排序.
    int[] arr = {2, 3, 5, 7, 8, 9, 11, 12, 15};
    // int[] arr = {15, 12, 11, 9, 8, 7, 5, 3, 2};
    
    int m = 3;
    
    // int index = search(arr, m);
    
    int index = binarySearch(arr, m, 0, arr.length - 1);
    
    System.out.println(index);
    
  }
  
}