题目三：在有空字符串的有序字符串数组中查找 ：有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串（肯定不是空字符串）的索引
思路：看到数组有序，首先应该要想到用二分法来去做，框架要先搭建出来，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);
}
}
觉得越来越有些上头了，奥利给！
————————————————
