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

Java二分查找

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

需求

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

思路分析：

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

1.mid=(left+right)/2

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

• findval>arr[mid]说明你要查找的数字在mid的右边，因此需要递归的向右进行查找
• findval<arr[mid]说明你要查找的数字咋mid的左边，因此需要递归的向左进行查找
• findval==arr[mid]说明找到，就返回

什么时候需要结束递归？

1.找到了数据就结束递归

2.递归完整个数组，仍然没有找到findval，也需要结束递归 当left>right就需要退出

代码实现

/**
 * 二分查找
 * 使用二分查找的前提 数组必须有序  从小到大 从大到小都可以
 *
 * @create: 2021/10/2
 * @author: Tony Stark
 */
public class BinandroidarySearch {
    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 rigZuzqrht,int findVal){
        //当left大于right时说明递归了整个数组但是没有找到
        if (left>right){
            return -1;
        }
        //中间值的下标
        int mid=(left+right)/2;
        //中间值
        int midVal=arr[mid];
   php     //如果要找的值大于中间值   向右递归  现在数组是从小到大  所以向右递归
        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

到此这篇关于Java数据结构与算法之二分查找详解的文章js就介绍到这了,更多相关Java二分查找内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！