二分查找算法解析

目录1. 二分查找适用场景2. 如何实现二分查找(核心思想)3. 二分查找 Java 代码演示1. 二分查找适用场景通常情况下使用二分查找可以确定想要查询的数据是否存在于某个数组中或者集合中。此外使用二分查找的前提是要查询的数组内数据的顺序必须是有序的顺序既可以从小到大排列也可以从大到小都可以排列只是代码稍微有些不同但核心解体思想都是一样的。2. 如何实现二分查找(核心思想)二分查找的核心思路就是每次砍掉一半的数据时间复杂度为 logn是一个比较优秀的算法时时间复杂度。例如一个数组中存放了9个数据我们要查找的数据是52那么就让52与数组中间的数据进行比较即4索引处的数据比较之后得出结果会分为以下三种情况。情况一如果取4索引处的数与要查询的数52做对比若恰好相等则说明4索引处的数据就是要查找的数据52情况二如果4索引处的数据大于52则说明要查找的数据在数组的左半边循环上面的查找思路再取中间的数据与52做对比直到查找到要查询的数据如果循环查找结束仍然没有与之匹配的值则说明要查找的数据在当前数组中不存在情况三如果4索引处的数据小于52则说明要查找的数据在数组的右半边再取中间的数据与52做对比循环上面的查找思路直到查找到要查询的数据如果循环查找结束仍然没有与之匹配的值则说明要查找的数据在当前数组中不存在此外我们学习的二叉树红黑树它们的检索的复杂度都是 logn遇到一个节点会选择左子树或者有字数直到查询到结果为止。3. 二分查找 Java 代码演示// 定义成一个静态方法方便以后的调用 // 方法参数分别传入一个待查询的数组 arr 和待查询的值 number // 以数组从小到大排列为例 // 方法返回值为要查询的数在数组中所在的索引值而非数值 public static int search(int[] arr, int number) { // 定义最小值变量 min 等于数组的最小值索引 int min 0; // 定义最大值变量 max 等于数组的最大值索引 int max arr.length - 1; // while死循环 while (true){ // 如果 min max说明要查找的数据在数组中不存在 if (min max){ return -1; } // 定义中间变量 middle int middle (min max) / 2; // arr[middle] number说明要查找的数在左边 if (number arr[middle]){ // 将最大值赋值为 middle 左边的第一个数据重新计算 middle max middle -1; // arr[middle] number说明要查找的数在右半边 }else if (number arr[middle]){ // 将最小值赋值为 middle 右边的第一个数据重新计算 middle min middle 1; }else { // 上面都不符合则当前值即为要寻找的值 return middle; } } }