本文是【常用算法思路分析系列】的第五篇，总结二分搜索相关的高频题目和解题思路。本文分析如下几个问题：1、求数组局部最小值问题；2、元素最左出现的位置；3、循环有序数组求最小值；4、最左原位；5、完全二叉树计算结点数；6、快速N次方。

本系列前四篇导航：
【常用算法思路分析系列】排序高频题集
 【常用算法思路分析系列】字符串高频题集

二分搜索的重要提醒：

一般我们选择中点进行搜索，会写成mid = (left + right) / 2;但是当数据很大的时候，下标(left + right)就可能出现溢出的情况，此时，更安全的一种写法是：mid = left + (right - left) / 2;

1、求数组局部最小值位置

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。

思路： 解题思路其实就是根据局部最小的定义来求解。首先，拿到一个数组后，考虑两端的情况，初始端arr[0] < arr[1] ，如果arr[0] < arr[1]则直接返回0；考察末尾段arr[N-1] < arr[N-2] ，如果arr[N-1] < arr[N-2]，则返回N-1；如果arr[0] > arr[1],则从0位置往后（右）看，数组是递减的，如果arr[N-1] > arr[N-2]，则从N-1处往前（左）看，数组也是递减的，说明符合条件的中中间位置，则考察中间位置mid = (left + right) / 2; 类似二分搜索的划分。如下：

public int getLessIndex(int[] arr) {
        if(arr == null || arr.length == 0){
            return -1;
        }
        if(arr.length == 1 || arr[0] < arr[1]){
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid  = 0;
        while(left < right){
            mid = (left + right) / 2;
            if(arr[mid] > arr[mid - 1]){
                right = mid - 1;
            }else if(arr[mid] > arr[mid + 1]){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return left;
    }

或者使用递归的写法，如下：

public int getLessIndex(int[] arr) {
        if(arr == null || arr.length == 0){
            return -1;
        }
        if(arr.length == 1){
            return 0;
        }
        return getLess(arr, 0, arr.length - 1);
    }

    private int getLess(int[] arr, int left, int right) {
        if(left == right){
            return left;
        }
        if(arr[left] < arr[left + 1]){
            return left;
        }
        if(arr[right] < arr[right - 1]){
            return right;
        }
        int mid = (left + right) / 2;
        if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]){
            return mid;
        }
        if(arr[mid] > arr[mid - 1]){
            return getLess(arr, left + 1, mid - 1);
        }else if(arr[mid] > arr[mid + 1]){
            return getLess(arr, mid + 1, right - 1);
        }
        return left;
    }

时间复杂度为O(logN)。上面这个例子说明，二分搜索并不一定只在数组有序的时候才可以用，只要我们在查找的时候发现，可以留下一半，淘汰另一半，就可以使用二分搜索。

2、元素最左出现的位置

对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。

给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。

思路： 由于数组有序，考虑用二分搜索法快速定位到数组中值为num位置处，找到后num后，因为数组有序递增，在num左边继续遍历，找到最左边的num位置，如下：

public int findPos(int[] arr, int n, int num) {
        if(arr == null || arr.length == 1){
            return -1;
        }
        int res = -1;
        int left  = 0;
        int right = arr.length - 1;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(arr[mid] > num){
                right = mid - 1;
            }else if(arr[mid] < num){
                left = mid + 1;
            }else {//arr[mid] == num
                res = mid;
                //因为需要寻找最左边的，而数组也是有序的，因此，还需要往mid左边寻找最左的一个num值位置
                right = mid -1;
            }
        }
        return res;
    }

3、循环有序数组求最小值

对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。

给定数组arr及它的大小n，请返回最小值。

测试样例：

[4,1,2,3,3],5

返回：1

思路：

（1）首先设置好下标，left=0，right=arr.length-1，如果arr[left] < arr[right]，由于数组有序，则arr[left]即为最小值，此时数组没有循环；

（2）当arr[left] >= arr[right]时，即数组为循环状态，开始二分搜索，找到中间位置mid = (left + right) / 2;如果arr[left] > arr[mid]，说明最小值一定在mid左半部分；

（3）如果arr[mid] > arr[right]，说明最小值一定出现在mid右半部分，否则，arr[left] <=arr[mid]，arr[mid] <= arr[right]，又arr[left] >= arr[right]，由三个条件==> arr[left] == arr[right] == arr[mid]。

此时，需要用遍历的方式在left-->right的区间寻找最小值。（或者说，因为arr[left] == arr[right] == arr[mid]，说明在[left,mid]区间内，必定有最小值，再在这个区间遍历搜索）

public static int getMin(int[] arr, int n) {
        if(arr == null || arr.length == 0){
            return -1;
        }
        if(arr.length == 1){
            return arr[0];
        }
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        //下面是arr[left] >= arr[right]的情形，即数组为循环状态
        while(left < right){
            if (left == right - 1) {
                break;
            }
            if(arr[left] < arr[right]){
                return arr[left];
            }
            mid = (left + right) / 2;
            if(arr[left] > arr[mid]){//最小值一定在mid左半部分
                right = mid;
                continue;
            }else if(arr[mid] > arr[right]){//最小值一定出现在mid右半部分
                left = mid;
                continue;
            }else{
                //这种情况下，arr[left] <=arr[mid]，arr[mid] <= arr[right]，又arr[left] >= arr[right]，由三个条件==> arr[left] == arr[right] == arr[mid]
                //此时，需要用遍历的方式在left-->right的区间寻找最小值
//                int min = arr[left];
//                for(int i = left; i <= right; i++){
//                    if(arr[i] < min){
//                        min = arr[i];
//                    }
//                }
//                return min;
                while(left < mid){
                    if (arr[left] == arr[mid]) {
                        left++;
                    } else if (arr[left] < arr[mid]) {
                        return arr[left];
                    } else {
                        right = mid;
                        break;
                    }
                }
            }
        }
        return Math.min(arr[left], arr[right]);
    }

4、最左原位

有一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。

给定有序数组arr及它的大小n，请返回所求值。

测试样例：

[-1,0,2,3],4

返回：2

思路： （1）先考察数组的两端，开始端如果arr[left] > n-1;或者，末端arr[right] < 0;则直接返回-1；（2）再通过二分搜索思想，mid = (left + right) / 2;比较arr[mid]和mid的值：当arr[mid]>mid时，arr[i] = i的值只可能在mid左边；当arr[mid]<mid时，arr[i] = i的值只可能在mid右边；
当arr[mid]==mid时，继续寻找最左边arr[i] = i的值；

代码如下：

public int findPos(int[] arr, int n, int num) {
        if(arr == null || n == 0){
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        if(arr[left] > n - 1 || arr[right] < 0){
            return -1;
        }
        int mid = 0;
        int res = -1;
        while(left <= right){
            if (arr[left] > left || arr[right] < right) {
                break;
            }
            mid = (left + right) / 2;
            if(arr[mid] > mid){
                right = mid - 1;
            }else if(arr[mid] < mid){
                left = mid + 1;
            }else{
                res = mid;
                right = mid - 1;
            }
        }
        return res;
    }

5、完全二叉树计数

给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

给定树的根结点root，请返回树的大小。

思路： （1）首先一直遍历到根节点的左子树的最左边，得到树的高度high；（2）再遍历根节点的右子树的最左边，得到右子树的高度rightHigh；（3）如果high==rightHigh，表示根节点的左子树为满二叉树,高度为high，此时左子树可以直接根据满二叉树的性质求出节点数量，再对右子树递归遍历；（4）如果high!=rightHigh，表示根节点的右子树为满二叉树,高度为high - 1，此时右子树可以直接根据满二叉树的性质求出节点数量，再对左子树递归遍历；代码如下：

public int count(TreeNode root) {
        if(root == null){
            return 0;
        }
        int high = 0;
        TreeNode node = root;
        while(node != null){
            high++;
            node = node.left;
        }
        int rightHigh = 0;
        node = root;
        while(node != null){
            rightHigh++;
            node = node.left;
        }
        if(high == rightHigh){//表示根节点的左子树为满二叉树,高度为high - 1
            return (int) (Math.pow(2, high - 1)) + count(root.right);
        }else{
            return (int) (Math.pow(2, rightHigh - 1)) + count(root.left);
        }
    }

6、快速N次方

如何更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1)，得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。

给定k和n，请返回k的n次方，为了防止溢出，请返回结果Mod 1000000007的值。

测试样例：

2,3

返回：8

思路： 以10^13为例，首先我们将13以二进制表示如下：0000 1101 10^13 = 10^1 * 10^4 * 10^8
我们根据二进制的长度，依次获取 10^1
10^2 = 10^1 * 10^1；
10^4 = 10^2 * 10^2;
10^8 = 10^4 * 10^4;
... 在这个过程中，如果二进制位上为1，则累乘起来，代码如下：

public int getPower(int k, int N) {
        if(k == 0){
            return 0;
        }
        if(k == 1 || N == 0){
            return 1;
        }
        long modNum = 1000000007;
        long res = 1;
        long temp = k;
        for(; N > 0; N >>= 1){
            if((N & 1) != 0){
                res *= temp;
            }
            temp = (temp * temp) % modNum;
            res = res % modNum;
        }
        return (int) res;
    }

下一篇将是与二叉树相关。

顶: 0

踩: 0

源码搜藏网

首页 > 开发教程 > 软件工程 >

【常用算法思路分析系列】与二分搜索相关高频题

创建时间：2016-06-12 17:36

1、求数组局部最小值位置

2、元素最左出现的位置

3、循环有序数组求最小值

4、最左原位

5、完全二叉树计数

6、快速N次方

相关内容

热门推荐