二分法的时间复杂度计算_二分法时间复杂度

先说下定义O(log2n)与O（n)的区别

O(log2n)含义说明：

比如123456789，你要找2，首先查中间元素5，大于2，所以直接排除掉5右边的6789，然后在1234里继续二分查找。每次排除1/2的元素，所以是O(log2n)。

O（n)含义说明：

n是元素的个数，O（n)意味着你把每个元素都访问一遍，这样你当然可以找到要查找的数了。但是对于有序数组，没必要这样遍历整个数组。

再说下时间复杂度：

总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。 

由于n/2^k取整后>=1，即令n/2^k=1， 

可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)。

总结一下就是：

二分法的关键思想是   假设该数组的长度是N那么二分后是N/2，再二分后是N/4……直到二分到1结束（当然这是属于最坏的情况了，即每次找到的那个中点数都不是我们要找的），那么二分的次数就是基本语句执行的次数，于是我们可以设次数为x，N*（1/2）^x=1；则x=logn,底数是2。

最后说二分法查找（binary search）：

也称作折半查找（half-interval search），每次划分一半进行下一步搜索，所以时间复杂度无非就是while循环的次数。

适用范围：

已经排好序的数组

Java 实现：

定义两个变量，一个low,一个high,则mid=(low+high)/2

    public static void main(String[] args) {
        int[] arr= {30,20,50,10,80,9,7,12,100,40,8};
        Arrays.sort(arr);//{7,8,9,10,12,20,30,40,50,80,100};
        System.out.println(Arrays.toString(arr));
        System.out.println(twoff(arr,40));
    }
 
    public static int twoff(int[] arr, int value) {
        //定义边界
        int low = 0;
        int high = arr.length - 1;
 
        while ((low <= high) && (low <= arr.length - 1)
                && (high <= arr.length - 1)) {
            int mid=(low+high)/2;
            if(value==arr[mid]) {
                return mid;
            }
            if(value>arr[mid]) {
                low=mid+1;
            }
            if(value<arr[mid]) {
                high=mid-1;
            }
        }
        return -1;//没有找到返回-1
    }

总结一下，简单理解就是二分都是以2为底n的对数。