数据结构与算法之二分查找

    2.1findval>arr[mid]说明你要查找的数字在mid的右边，因此需要递归的向右进行查找

    2.2findval<arr[mid]说明你要查找的数字咋mid的左边，因此需要递归的向左进行查找

    2.3findval==arr[mid]说明找到，就返回

/**
 * 二分查找
 * 使用二分查找的前提 数组必须有序  从小到大 从大到小都可以
 *
 * @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;
    }
}

5