二分查找算法基础知识、关键案例和插图

1。大O表示法：

指示算法的速度有多快，用于指出随数量的增大，算法的所需步骤增加的速度，常见的大O运行时间(时间复杂度)：
O(1)表示常数阶时间复杂度
O(log n)，也叫对数时间复杂度，这样的算法包括二分查找。
O(n)，也叫线性阶时间复杂度，这样的算法包括简单查找。
O(n * log n), （n*对数复杂度）
O(n^2)，平方阶时间复杂度
O(n!)，阶乘阶时间复杂度
复制代码

当n越来越大时，算法效率图为：

关键点

• 1。二分查找法只适合从有序队列（如数字、字母等）开始查找，对队列排序后查找
• 2。二分查找法的运行时间是对数时间O(㏒?n)，即找到需要的目标位置最多只需要只需要㏒?n步。假设从[0,99]的队列中找到目标号码30（100个号码，即n=100），那么搜索步数为㏒2100，即到必须搜索7次(2^6
• 3。简单查询（遍历查询）的运行时间是线性时间O(n)，假设从[0,99]队列中找到目标数30（n=100），则最多 D '所需的搜索步骤数为 100
• 4。如果容器中的数量非常少，两次搜索可能就没用了。如果数量很大的话差异就很大。例如，假设搜索和比较步骤一次需要1秒，如果容量为100,000，O(n)需要100,000秒，大约是27.8小时，而logn只需要2^16
• 5、最坏情况的时间复杂度用表示，表示最大步数

情况

从容器中从1到99中查找指定数字；

java实现:
A：简单查找法，即遍历查找，全部遍历直到找到指定的数便停止

/**
 * 简单查找
 * @param array    传入存放全部数据的容器
 * @param target   需要查找的目标数
 * @return
 */
public Integer search(Integer[] array,int target){
    for(int i=0;i<array.length;i++){
        if(array[i] == target){
            return i;
        }
    }
    return null;
}

B：二分查找法

/**
 * 二分查找法
 * @param array   传入存放全部数据的容器
 * @param target  需要查找的目标数
 * @return
 */
public Integer searchDichotomy(Integer[] array, int target){
    int low =0;
    int hight=array.length-1;
    while(low<=hight){                 //遍历还没结束
        int mid = (low+hight)/2;       //取中间值mid点位置
        if(array[mid]==target){        //寻找到目标数
            return mid;
        }
        if(array[mid] > target){        //如果中间值大于目标数，则将highr点位置移动mid位置左边
           hight = mid-1;
        }
        if(array[mid] < target){       //如果中间值小于目标数，则将low点位置移动mid位置右边
            low = mid+1;
        }
    }
    return null;
}
复制代码

说明：

假设容器为[1,99]，一共有99个数字。你必须明白，由于时间复杂度是最坏的情况，二分查找最多需要 7 步，而简单的遍历方法最多需要 99 步（如果搜索数字 99）；

要搜索当前个，消耗的步骤可能不一样，但不会超过时间复杂度

步骤图如下（[1, 99]，即n=99，搜索次数为30）：

时间复杂度计算过程：

参考：https://blog.csdn.net/frances_han/article/details/6458067 二分查找的基本思想是将n个元素分成近似相等的两部分split，比较a[n/2]与x，若x=a[n/2]，求x，算法结束；如果xa[n/2]，则只需在数组a的右半部分中查找x即可。时间复杂度无非就是迭代次数！总共有 n 个元素，逐渐为 n、n/2、n/4、....n/2^k，其中 k 是循环次数。由于您的 n/2^k 四舍五入 >= 1，这意味着 n/2^k=1 可以通过 k=log2n 获得（这是 n 以 2 为底的对数）。因此，时间复杂度可以表示为O() = O(logn)。