目录

@(二分搜索法)

例如：

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

一个数组,我们要从中找到5在其中的位置，最简单就是如下：

for(int i=0;i

这种方法用大O表达法分析[^1]的话，

i=0；的频度为1

i<a.length的频度为n； ==a.length的长度不是固定的==

if语句也执行了n次

时间复杂度为：

T（n）= 1+ 2*n；

可以写为T（n）=O（n）

使用二分搜索法的话：

~非递归实现~

public static void main(String[] args) {        // TODO Auto-generated method stub        int a[]= {1,2,3,4,5,6,7,8};        System.out.println(binarySearch(a, 7));        System.out.println(binarySearchp(a, 7,0,a.length-1));    }    /**     * 非递归     * @param a  需要查询的数组     * @param x 需要查询的值     * @return 数组中的索引     */    public static int binarySearch(int a[],int x) {        int l=0,r=a.length-1;        while(l<=r) {            int m=(l+r)/2;            if(a[m]==x) {                return m;            }else if(a[m]>x) {                r=m-1;                            }else {                l=m+1;            }                    }        return -1;    }

~递归实现~

/**     * 递归     * @param a 数组     * @param x 需要查询的值     * @param l 左边的指针     * @param r 右边的指针     * @return  在数组中的索引     */    public static int binarySearchp(int a[],int x,int l,int r) {            int m=(l+r)/2;            int res=0;            if(a[m]==x) {                return  m;            }else if(a[m]>x) {                return binarySearchp(a, x,l,m-1);            }else {                return binarySearchp(a, x,m+1,r);            }                }     public static void main(String[] args) {        // TODO Auto-generated method stub        int a[]= {1,2,3,4,5,6,7,8};        System.out.println(binarySearch(a, 7));        System.out.println(binarySearchp(a, 7,0,a.length-1));    }

==用大O分析二分搜索的算法，可见每次执行一次算法的while循环，搜索数组减少一半，因此最坏情况被执行了O（logn）==

[^1]:大O表示法主要用来

计算算法的时间复杂度