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

使用前提：二分查找需要在有序数组中进行查找

需求

请对一个有序数组进行二分查找{1,8,10,89,1000,1024}，输入一个数字看看该数组中是否存在此数，并且求出下标，如果没有就返回“-1”

思路分析：

首先确定该数组的中间下标

1.mid=(left+right)/2

2.然后让需要查找的数findval和arr[mid]比较

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

    2.2findval 
什么时候需要结束递归？
 
1.找到了数据就结束递归
 
2.递归完整个数组，仍然没有找到findval，也需要结束递归 当left>right就需要退出
 
代码实现
 
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);
    }

    
    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 
输出
 
5