二分查找（2）

最左原位

原位指的是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;
    }

思路：

对于有序数组来说，直接可以否定两种情况：

1. arr[left]>right
   如果首元素都大于right，那么后序元素肯定都是大于right的，那么arr[mid]肯定大于right。而right>=mid就不可能有arr[mid]==mid的情况。
2. 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;
    }