一、注意：
（1）有序数组，时间复杂度O(logn) while(low<=high) mid=(left+right)/2
（2）有序循环数组（有序数组左边任意长度移到右边，比如1 2 3 4 5的变形3 4 5 1 2就是有序循环数组。）
（3）Mid=(left+right)/2是经典写法，但当left或right特别大时可能溢出，所以安全写法是mid=left+(right-left)/2;
（4）二分查找不一定是有序数组的，只要在查找过程中能够留下一半抛弃一半，就符合这种方法。
二、练习题：
（1）局部最小：二分查找 时间复杂度O(logn)
a长度为1时，a[0]是局部最小。a的长度为N(N>1)时，如果a[0]<a[1]，那么a[0]是局部最小；如果a[N-1]<a[N-2]，那么a[N-1]是局部最小；如果0<i<N-1，既有a[i]<a[i-1]又有a[i]<a[i+1]，那么a[i]是局部最小。 给定无序数组a，已知a中任意两个相邻的数都不相等，写一个函数，只需返回a中任意一个局部最小出现的位置即可。
思路：首先，判断数组的两边是否为局部最小即a[left]和a[right]。
然后，判断mid=(left+right)/2是否局部最小。有以下情况：
Left 和right是局部最小时，那么从left向右看数组是向下的，从right向左看数组也是向下的。此时：
1）如果mid比m-1,m+1都大，那么mid向左向右看都是向下的，所以左右两侧必然都存在局部最小。
2）如果mid比m-1,m+1都小，那么mid是局部最小，返回mid即可
3）如果mid比m-1大，m+1小，那么从mid向左看数组是向下的，则左半部分必定存在局部最小。<m-1，>m+1也是一样。
public class Solution { public int getLessIndex(int[] arr) { int len = arr.length; if (len == 0) return -1; if (len == 1) return 0; if (arr[0] < arr[1]) return 0; if (arr[len-1] < arr[len-2]) return len-1; int result = getLess(arr, 1, len-2); return result; } private int getLess(int[] arr, int left, int right) { while (left <= right) { int mid = left+(right-left)/2; if (arr[mid+1] > arr[mid] && arr[mid-1] > arr[mid]) { return mid; }else if (arr[mid] > arr[mid-1]) { right = mid-1; }else if (arr[mid] > arr[mid+1]) { left = mid+1; } } return -1; } }-------------------------------------------------------------------------------------------------------------
（2）有序数组a[n],再给定一个整数num，请在a中找到num这个数出现的最左边的位置。
给定一个数组a及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。 如：数组[1,2,3,3,3,4,4,4,4,4,4,4] num=3,则返回2
Static int res=-1记录3最后一次出现的位置。
二分查找mid=4，则抛弃右边；继续查找 mid=3，记录此时3的位置res=3;继续二分mid=2抛弃左半部分，mid=3 更新res=2.
public class LeftMostAppearance { static int res=-1; public int findPos(int[] a, int n, int num) { // write code here binSearch(a,0,n-1,num); return res; } public void binSearch(int[]a ,int left,int right,int num){ if(left<=right){ int mid=left+(right-left)/2; if(a[mid]==num) { res=mid; binSearch(a,left,mid-1,num); }else if(a[mid]>num){ binSearch(a,left,mid-1,num); }else{ binSearch(a,mid+1,right,num); } } } }-------------------------------------------------------------------------------------------------------------
（3）有序循环数组最小值：
有序循环数组：有序数组，左边x个数移到右边，如1 2 3 4 5的变形 4 5 1 2 3就是有序循环数组，利用二分查找找到最小值，时间复杂度O(logn)，最坏情况O(n) 最好别用递归方法，小李啊
1）如果a[left]<a[right] 说明[left,right]之间是有序的不包括循环部分，此时该区间最小值为a[left]。
2）如果a[left]>=a[right]说明[left,right]之间包括循环部分，如[4 5 1 2]，则进行二分查找，mid=(left+right)/2：（即这种情况就是最小值在循环部分）
如果a[right]<a[mid]则说明右半边[mid,right]是包含循环部分的，最小值该在右半边。如 4 5 6 7 8 9 1 2 3，mid=8，right=3
如果a[left]>a[mid]说明左半边是包含循环的，最小值在[left,mid]
如果以上两个条件都不满足，说明a[left]=a[mid]=a[right],例如{2 2 2 1 2 2 2 2} 不符合二分查找，用遍历方式查找left~right部分。
public class MinValue { public int getMin(int[] a,int n) { if(a==null||n==0) return -1; if(n==1) return a[0]; int left=0; int right=n-1; while(left<right){ if(left==right-1) break;//将最小值锁定在 a[i]和a[i+1]上 if(a[left]<a[right]) return a[left];//left到right是顺序的 int mid=left+(right-left)/2; if(a[left]>a[mid]){//最小值是循环的开头，在左半边, right=mid;//a[mid]可能是最小值 continue; } if(a[mid]>a[right]){//循环在右半边 left=mid; continue; } //不符合上述两种情况，//a[left]=a[mid]=a[right]情况 遍历法 while(left<right){ if(a[left]==a[mid]){ left++; }else if(a[left]<a[mid]){ return a[left]; }else{ right=mid; break; } } } return Math.min(a[left],a[right]); } }
-------------------------------------------------------------------------------------------------------------
（4）完全二叉树的节点计数：时间小于O(N)
1）完全二叉树左子树的深度ldepth.(找最左节点)
2）二叉树右子树的深度rdepth.（找root.right的最左节点）
3）如果ldepth==rdepth，说明左子树是一棵满完全二叉树。总节点数=左子树个数+head+递归求右子树的节点
4）如果ldepth>rdepth，head的右子树是满的，总结点数=右子树个数+head+递归求左子树节点。
使用遍历的方式，时间复杂度为O(n),使用二分查找方式时间为O(h^2)=O((logn)^2)
public class CountNodes { public int count(TreeNode root) { if(root==null) return 0; int nodeCount=0; int lDepth=0; TreeNode cur=root.left; while(cur!=null){//记录左子树的深度 lDepth++; cur=cur.left; } int rDepth=0; cur=root.right; while(cur!=null){//记录右子树右节点的深度 rDepth++; cur=cur.left; } if(lDepth==rDepth){//左子树是一棵满二叉树 nodeCount=(int)Math.pow(2,lDepth)+count(root.right); }else{//ldepth>rdepth 右子树是一棵满二叉树 nodeCount=(int) Math.pow(2,rDepth)+count(root.left); } return nodeCount; } }-------------------------------------------------------------------------------------------------------------
（5）快速求k^n：时间复杂度O(logN)
题目：
求一个整数k的n次方。两个整数相乘并得到结果的时间复杂度为O(1)，得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。
给定k和n，请返回k的n次方，为了防止溢出，请返回结果Mod 1000000007的值。
思路：首先将指数n->二进制，以10^75为例
75的二进制数是1001011, 分别对应10^64 ，10^32，10^16，10^8 ，10^4 ，10^2 ，10^1（注意这里从10^1开始，不是10^0）,其中10^n是不是10^75的分式，与75的二进制相同，1则是0则不是。
所以10^75= 10^64 * 10^8 * 10^2 *10^1
k^n是n的二进制每次右移一位，k每次自乘，但是最终结果是否乘以k自乘的结果看n是否为1，为1结果乘以k自乘的结果，为0则不乘
import java.util.*; import java.math.BigInteger; public class QuickPower { public int getPower(int a, int n) { BigInteger res = BigInteger.valueOf(1); //BigInteger是不可变的任意精度的整数。所有操作中，都以二进制补码形式表示 BigInteger BigInteger tmp = BigInteger.valueOf(a); for (; n != 0; n >>= 1) {//n每次右移1位 相当于除2 if ((n & 1) != 0) {//n的二进制树为1对应的位置要乘以当前k值 res = res.multiply(tmp); } tmp = tmp.multiply(tmp);//tmp就对应 a^1,a^2,a^3... res = res.mod(BigInteger.valueOf(1000000007));//防止溢出 tmp = tmp.mod(BigInteger.valueOf(1000000007)); } return res.mod(BigInteger.valueOf(1000000007)).intValue(); } }
