在有空字符串的有序字符串数组中查找 ：有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串（肯定不是空字符串）的索引

思路：看到数组有序，首先应该要想到用二分法来去做，框架要先搭建出来，begin、mid、
end、以及mid>要找的元素,end=mid-1,mid<时，begin=mid+1.
 其次，考虑到时字符串，在等于空的时候，用equals方法，在比较的大小的时候，用
 compareTo方法。

代码：

package LanQiaoKnowledge;

public class 在有空字符串的有序数组中查找 {
                    //利用二分法的思想
    static int indexof(String[] arr,String p) {
        int begin=0;
        int end=arr.length-1;
        while(begin<=end) {          //begin往右走，end往左走
            int mid=begin+((end-begin)>>1);
            while(arr[mid].equals("")) {        //中间元素为空的情况，将指针往右面移动一个。再重新比较
                mid++;
                //坑
                if(mid>end) {
                    return -1;            //另外一个出口
                }
            }
            if(arr[mid].compareTo(p)>0) {
                end=mid-1;
            }
            else if(arr[mid].compareTo(p)<0) {
                begin=mid+1;
            }else {
                return mid;
            }
        }
        
        return -1;
    }
    public static void main(String[] args) {
        String s[]= {"a","ab","","bd","f"};
        int res=indexof(s,"bd");
        System.out.println(res);
        
        
    }
}


=================================================================

优化a^n

思路：传统的用循环的写法，写出来的复杂度为O（n），可以将O（n）优化到O（log n）。
 思路：log（n）的话，结合之前来看，是将本来的问题每次折半，上楼梯或者下楼梯的时候
 一次上一半或者下一半。在求a^n时，每次将n翻一倍，例如将2^n,设定第一次指数为1，翻
 第一次变成2，第二次变成4，第三次8，剩下的7次再交给第二个递归去做。这样就可以将
 时间复杂度优化为O（log n）。

代码：

package LanQiaoKnowledge;

public class 求a的n次幂 {
        //传统的循环写法
static int pow1(int a,int n) {
    
    int res=1;
    for(int i=0;i<n;i++) {
        res=res*a;
    }
    return res;
}
        static int pow2(int a,int n) {
            if(n==0) {                //出口
                return 1;
            }
            int res=a;                        //a不能作为一个变量，所以设定一个数将a赋值给它
            int exit=1;                                //初始的幂
            while((exit<<1)<=n) {                    //循环能够继续的条件为每次幂翻倍以后仍然小于等于n
                res=res*res;
                exit=exit<<1;                                //每次一个循环过后，幂都要翻倍
            }
            //补差值
            return res*pow2(a,n-exit);                //如果n不能准确的翻倍来得到。不补差值，再调用递归
        }

public static void main(String[] args) {
    int answer=pow1(2,15);
    System.out.println(answer);
    System.out.println("*************");
    int answer1=pow2(2,15);
    System.out.println(answer1);
}
}