最左原位
原位指的是arr[m]==m的位置。找出一个有序单调不减数组中最左原位，若无返回-1.
int findPos(vector<int> arr, int n) {
// write code here
if(n<1)
return -1;
int left=0,right=n-1;
//直接判断不存在的两种情况
if(arr[left]>left)
return -1;
if(arr[right]<right)
return -1;
//核心：判断mid值和mid的关系
//和以前找最左元素的情况类似，为了防止死循环，判断条件不含等
while(left<right){
int mid=left+(right-left)/2;
if(arr[mid]>mid)
right=mid-1;
if(arr[mid]==mid)
right=mid;
if(arr[mid]<mid)
left=mid+1;
}
if(arr[left]==left)
return left;
else
return -1;
}
思路：
对于有序数组来说，直接可以否定两种情况：
- arr[left]>right
如果首元素都大于right，那么后序元素肯定都是大于right的，那么arr[mid]肯定大于right。而right>=mid就不可能有arr[mid]==mid的情况。 - arr[right]<left
同理。
如果上述情况不出现，那么就判断arr[mid]与mid的关系。
例如
下标：0 1 2 3 4 5
数值：0 1 2 4 5 6
我们来看下标是3的数arr[3]==4.因为数组的下标步长是1，整数的步长最少是1，那么如果arr[3]>3（意味着arr[3]>=4），那么arr[4]一定大于4。同理，后面的部分一定是没有原位数的。所以要把区间锁定在前半部分。
同理，arr[mid]<mid的时候，要把区间锁定在后半部分。
因为可能不止一个原位数，所以在arr[mid]==mid的时候，区间调整时不应排除掉mid.
完全二叉树的节点数
对于完全二叉树来说，元素只会在最后一层的右侧缺失。所以利用这个性质我们可以在O(logN)内计算节点数。
对于一个完全二叉树，我们统计一下它的左子树的层数deepL和右子树的层数deepR.如果两者相等，意味着左子树是满的，就可以用满二叉树的公式算结点数。如果两者不等，意味着右子树是满的，同理用公式计算右子树结点数。递归下去直至根节点为空。
int count(TreeNode* root) {
//如果root为空，返回结点数为0
if(root==nullptr)
return 0;
int deepL=0,deepR=0;
TreeNode* p=root->left;
//求层数时，可以沿着左分支层层向下至空。
while(p){
deepL++;
p=p->left;
}
p=root->right;
while(p){
deepR++;
p=p->left;
}
if(deepL==deepR){
return 1+(1<<deepL)-1+count(root->right);
}else{
return 1+(1<<deepR)-1+count(root->left);
}
}
求幂
若两数相乘一次视作常数时间，求O(logN)内求解幂。
思路：
举一个例子，求10^32 ,如果32个10相乘一定很费事，但是如果我知道10^16 =U，那么10^32 就是U*U.
所以说，只需要求出10^1 -> 就知道10^2 -> 就知道10^4 ->就知道10^8 ->就知道10^16 ->就知道10^32.
一般的，对于N 来说，不过是1,2,4,8,16.32...的一些数相加而已。所以说，10^N 不过是10^1 10^2 10^4 ...的一些数相乘。为了直观，可以把N表示为二进制。二进制哪一个位上是1，就意味着它的乘数里面有该位对应的数。
//求k的N次方。
long long getPower(int k, int N) {
//本身是个累乘的过程
long long res=1;
//基底一开始的时候是k，然后每次循环base本身做乘方。
long long base=k;
while(N){
//每次bit取N的最后一位，每次N右移一位，直至N为0.相当于依次取出N的最右位
int bit=N%2;
if(bit)
res*=base;
N>>=1;
base*=base;
}
return res;
}
