二分法查找Java实现

原理：二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下：

1：首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

2：如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤1的操作。

3：如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。

代码实现：
非递归实现:

 public static void main(String[] args) {
        int[] arr = {3, 60, 63, 82, 85, 90, 99};
        //要查找的元素
        int number = 99;
        //定义数组最小索引
        int start = 0;
        //定义数组最长的索引
        int end = arr.length-1;
        boolean isFlag = true;
        while (start <= end) {
             int mid  = (start + end)/2;
             if (arr[mid]  == number)
             {
                 isFlag = false;
                 break;
             }
//            arr[mid]是最中间的值，说明在左侧
             else if (arr[mid] > number)
             {
                 end = mid - 1; 
             }
             else
             {
                 start = mid + 1;
             }
        }
        if (isFlag)
        {
            System.out.println("没找到");
        }
        else
        {
            System.out.println("找到了");
        }

    }

递归实现

 public boolean binarySearch(int[] arrs,int numebr,int start,int end){
        int middle = (start + end)/2;

        if (start <= end)
        {
            if (arrs[middle] == numebr)
            {
                return true;
            }
            else if (arrs[middle] > numebr)
            {
                binarySearch(arrs,numebr,middle-1,end);
            }
            else
            {
                binarySearch(arrs,numebr,start,middle+1);
            }
        }
        return false;
    }

递归方法的模板

public static void main(String[] args) {
        //定义一个数组
        //定义要查找的元素
        //定义数组最小索引，一般为0		start 
        //定义数组最长的索引，一般为数组.length，我喜欢用数组.length-1	end
        boolean isFlag = true;
        while (//start <= end，循环条件) {
             int mid  = (start + end)/2;
             if (arr[mid]  == //要查找的元素)
             {
                 isFlag = false;
                 break;
             }
//            arr[mid]是最中间的值，说明在左侧
             else if (arr[mid] > //要查找的元素)
             {
                 end = mid - 1; 
             }
             else
             {
                 start = mid + 1;
             }
        }
        if (isFlag)
        {
            System.out.println("没找到");
        }
        else
        {
            System.out.println("找到了");
        }

    }

二分法查找虽然简单，但偶尔还是会有点小问题
1、数组的最长索引是使用数组.length还是数组.length-1
2、循环条件是 <= 还是 <
3、mid是否要加减1，是否会溢出

注

初始化的长度为数组.length-1时，循环条件使用等于号，在给索引赋值的时候mid要加减1; 
初始化的长度为数组.length时，循环条件不使用等于号，在给索引赋值的时候mid不需要加减1;

mid是否会溢出？
建议写成mid = left + (right - left) / 2

最后

以上就是贪玩悟空为你收集整理的二分法查找Java实现的全部内容，希望文章能够帮你解决二分法查找Java实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。