我们在学习二分查找法基础版时会有疑惑

明明二分查找难以理解，我们为什么不选择暴力遍历呢

其实暴力遍历在算法里面叫做线性查找

让我们看看二次查找和线性查找的执行次数

可以采用以下两种方式

事后统计法

通过代码跑一遍 需要大量数据测并且对硬件有要求 不推荐

事前分析法

1.分析最差的执行情况

2.假设每行语句执行的时间是一样的

不然无法分析

即最差的情况就是执行到最后一行代码 for循环次数拉满

下面是线性查找

下面是二分查找

放一起

我们将这两种方法引入图片中

我们发现当数据很大时，二分查找所用的次数远远低于线性查找

时间复杂度

是用来衡量随着一个算法的执行，随着数据规模的增大，而增长的时间的成本

注：不依赖于环境因素 硬件cpu主频和内存读取速度与软件编译器

大O表示法

如图

渐进上界表示代码执行最差的情况

渐进下界表示代码执行最好的情况

大O表示法表示

用基本函数函数大于然后去掉系数

我们可以通过函数绘图工具找出表达式

如

线性查找

二分查找

总结

常见的大O表示法

O(1) 常量时间 说明算法时间不会随着数据规模而变化

O(log（n）)对数时间

O（n）算法时间与数据规模成正比

O(n*log(n))拟线性时间

O(n平方)平方时间

O(2的n次方)指数时间

O(n！)阶乘时间 时间复杂度最高

三种时间复杂度表示方法

空间复杂度

与时间复杂度类似，一般也使用大O表示法来衡量，一个算法的执行随数据规模增大，而增长的额外空间成本

算法执行需要额外占据的字节数

看到这里你是不是头晕了，头晕了是正常的，因为这些东西都是概念，我的标题还有一部分注意到了吗

给大家看一个二分查找的改动版，我们又叫他平衡版本

//导入Scanner包下的类
public class Main {

    public static void main(String[] args) {
        //创建Scanner类的对象
        Scanner sc=new Scanner(System.in);
        //定义数组的长度
        int n= sc.nextInt();
        //输入数组的数值
        int arr[]=new int[n];
        for (int i = 0; i < n; i++)
            arr[i]= sc.nextInt();
        //输入待查找数值
        int taget= sc.nextInt();
        //调用二分查找法
        binarySearch(arr,taget);
    }
    //访问修饰符public表示公有化方法 是权限最大的访问修饰符权限修饰符
    //即可以可以在同一个类，同一个类的其他方法，不同包下的子类，不同包下的其他类中使用
    //被static修饰的方法独立于该类的任何对象
    //也就是说，这些变量和方法不属于任何一个实例对象，而是被类的实例对象所共享;
    //其实意思就是都可以用
    public static int binarySearch(int a[], int target){
        //指定两个指针
        int i=0,j=a.length;
        while(1<j-i){
            int m=(i+j)>>>1;
            if(target<a[m])
                //右指针左移
                j=m;
            else
                //左指针右移
                i=m;
        }
        if(a[i]==target)
            //找到了
            return i;
        //没找到
        else return -1;
    };
}

我们分析一下他与二分查找基础版本的区别

如果元素在最左边要执行L次

那么元素在最右边要执行2L次

左边找元素成本低 因为只要比较一次就行

else if是造成不平衡的原因

左闭右开的区间，i指向的可能是目标，而j指向的不是目标

不在循环内找出，等范围内只剩i时，退出循环，在循环外比较a[i]和target

循环内的平均比较次数减少了

时间复杂度O-(log（n）)

因为渐近上界和渐近下界一样

所以我们用渐进紧界表示（就是O中间一横 上面有）

也算是一个缺点，可以忽略，从严格意义上不算是缺点