如何衡量算法好坏

1.事后测试法

都运行一遍看谁运行快，很依赖测试数据，也很依赖硬件。只有足够多的数据才能分析出算法好坏。

2.事前测试法

找到数据最差的执行情况。因此针对昨天的二分查找用一个线性比较来看看到底是哪种算法更优。

这是昨天的二分查找代码以及一个线性查找代码。

public static int binarySearch(int [] a,int target){
        int i = 0,j = a.length - 1;//设置指针
        while( i <= j){
            int m= ( i + j ) >>> 1;
            if(a[m] < target){
                i= m + 1;//目标在右
            } else if (target < a[m]) {
                j= m - 1;//目标在左
            }else{
                return m;//目标查找成功
            }
        }
        return -1;
    }

public static int lineSearch(int[] a,int target){
        for (int i = 0 ; i < a.length ; i++ ){
            if( a[i] == target){
                return i;
            }
        }
        return -1;
    }

很显然对于线性查找，最坏的情况是需要查找的数据是最后一个数据（这是一个有序数组）。所以对于线性查找。循环总进行的最差次数为n+1次。

此时我们令各个语句的运行时间都设定为t，因而对于各个语句可以计算在最坏情况下代码总运行代码的时间。对于线性查找而言，总次数为3*n+3。

对于二分查找，最坏的循环情况与元素个数有关

元素个数	循环次数
4-7	3
8-15	4
16-31	5
32-63	6
...	...

循环次数=

对于二分查找，总查找次数为。因而当数据个数增多时，二分查找时间是远远小于线性查找的。

在计算机中，可以用时间复杂度来衡量一个算法

用大O表示法来替代上述的循环次数，来得到一个更方便判断的式子。

现在我们对于一个式子f(n)，我们寻找他的渐进上界，从某个常数开始，c*g(n)会总大于f(n)，就记作O(g(n))。

因此对于,可以得到，当c=4时，表示为。

对于，表示为。

在表示过程中有这些规则。常量c都可以省略，多项式中的低次项都可以省略。对于不同底数的对数的底数都可以省略，对数的幂次（对数的幂数等于常量）都可以省略。

空间复杂度也可以衡量

对于二分查找算法，需要定义三个变量i，j，m。而在代码运算过程中都不会出现系的变量占用额外空间。因此他的空间复杂度为O（1）。

因此针对二分查找我们就有了如下思考

假设循环次数为X次，当我们要查询的数据在m的左边和m的右边有不同时，他们各自需要经历的判断语句次数不平衡。

public static int binarySearch2(int [] a,int target){
        int i = 0,j = a.length - 1;//设置指针
        while( 1 < j - i){
            int m= ( i + j ) >>> 1;
            if(a[m] < target){
                i= m ;//目标在右
            } else  {
                j= m ;//目标在左
            }

        }
        if (a[i] == target){
            return i;
        }else{
            return -1;
        }
    }

因此有了如上代码，while循环不断逼近目标target，当只剩一个数时走出循环，如果能匹配上target则输出查询成功，反之则失败。

而在java中有已经实现可引用方法

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

java中的查找失败时，返回-（low+1），是左边界+1，也就是提示这个不存在数据应该在数组中哪个位置插入。而为什么返回值是-(low+1)呢，当我查询的数在数组中没有且最小时，此时循环会结束，并且查找失败，此时i=0，m=0。此时为了区分到底是查找成功返回还是查找失败返回，因此对返回值-1进行处理，方便理解。

当数据中有多个相同数据时

对于我原先的代码，查找到的数据完全是打到哪个是哪个，非常不合适，因此有没有办法查找到最左边的相同数据。这也就是Leftmost查找。

public static int binarySearchLeftmost(int [] a,int target){
        int i = 0,j = a.length - 1;//设置指针
        int candidate = -1;//设置一个变量用来存储候选数据
        while( i <= j){
            int m= ( i + j )/ 2;
            if(a[m]<target){
                i= m + 1;//目标在右
            } else if (a[m]>target) {
                j= m - 1;//目标在左
            }else{
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

总体思路就是当查找到数据时，将这个数据的索引存储起来，继续往做查找是否还有其余相同的数据，如果有则覆盖，最后输出candidate就是最左边的数据。同理，也可以查找最右边的数据，也是类似的代码。

对上述代码修改，当查找成功时，输出i，即最左侧数据索引位置。当查找失败时，输出的i就是最接近数据的索引位置。

public static int binarySearchLeftmost(int [] a,int target){
        int i = 0,j = a.length - 1;//设置指针
        while( i <= j){
            int m= ( i + j )/ 2;
            if(a[m]<target){
                i= m + 1;//目标在右
            } else if (a[m]>=target) {
                j= m - 1;//目标在左
            }
        }
        return i;
    }