二分查找详解（Java）-Toy模板网

这篇具有很好参考价值的文章主要介绍了二分查找详解（Java）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、线性查找

在我们了解二分查找之前，我们先来了解线性查找

线性查找的思想：

二分查找java,算法与数据结构,算法,数据结构,排序算法

我们在对数组遍历的时候，通过每个值每个值的判断去实现我们的待查找的值是否存在当前数组中，如果存在就返回当前的索引。

代码实现：

public int findTarget(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

此时我们发现当前数组的顺序是无序的，当我们在有序数组中去查找目标数的时候会出现什么样的情况呢？

2、有序数组

int[] arr = {1,2,3,4,5,6,7,8,9,10};

对于上述的有序数组，线性查找时，当我们想查询的数为1时，此时索引正好为0，但是我们想查询的目标数为10的时候，此时我们需要遍历的10次，到数组的结尾，此时的效率就显得比较慢了，在对有序数组排序的时候我们就可以使用二分查找

2.1、二分查找

二分查找又叫折半查找，顾名思义，折半查找的意思就是每次查询的时候对数组折半，原理如下所示：

二分查找java,算法与数据结构,算法,数据结构,排序算法

我们此时进行比较，target = 4与arr[mid]的值，如果比mid位置的数大，我们只需在mid的右边进行查找，因为当前数组为有序数组，mid左边的数都是比mid小的数，所以左边的数我们无需考虑，此时下一步如下：

二分查找java,算法与数据结构,算法,数据结构,排序算法

当前计算的mid=4,即arr[mid]=5,此时的target<mid位置的值，所以我们只需再比较mid左边的值，详细步骤如下：

二分查找java,算法与数据结构,算法,数据结构,排序算法

此时计算的mid=min,此时再进行比较，发现我们需要查找的target的值等于当前mid的值，所以我们直接返回当前mid位置。

代码实现如下：文章来源地址https://www.toymoban.com/news/detail-522784.html

public int binarySearch(int[] arr, int target) {
        int max = arr.length -1;
        int min = 0;
        int mid = min + (max - min) / 2;
        while(min < max){
            if(arr[mid] == target){
                return mid;
            }
            if(arr[mid] < target){
                min = mid + 1;
                mid = min + (max - min) / 2;
            }
            if(arr[mid] > target){
                max = mid - 1;
                mid = min + (max - min) / 2;
            }
        }
        return -1;
    }

到了这里，关于二分查找详解（Java）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！