/**
 * 二分查找
 * 使用二分查找的前提 數組必須有序  從小到大 從大到小都可以
 *
 * @create: 2021/10/2
 * @author: Tony Stark
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1024};
        int i = binarySearch(arr, 0, arr.length - 1, 1024);
        System.out.println(i);
    }
    /**
     * 二分查找的方法
     * @param arr  數組
     * @param left   左邊的索引
     * @param right   右邊的索引
     * @param findVal  要查找的值
     * @return  如果找到就返回下標  ，沒有找到就返回-1
     */
    public static int binarySearch(int[] arr,int left,int right,int findVal){
        //當left大于right時說明遞歸了整個數組但是沒有找到
        if (left>right){
            return -1;
        }
        //中間值的下標
        int mid=(left+right)/2;
        //中間值
        int midVal=arr[mid];
        //如果要找的值大于中間值   向右遞歸  現在數組是從小到大  所以向右遞歸
        if (findVal>midVal){
              //向右遞歸
           return binarySearch(arr,mid+1,right,findVal);
        }else if(findVal<midVal){
            //如果要找的值小于中間值向左遞歸
            return binarySearch(arr, left,mid-1, findVal);
        }else if (findVal==midVal){
            //這種情況就是找到了那個數字
            return mid;
        }
        return -1;
    }
}