两道看似简单的高频算法面试题

前几天写了一篇 二分查找 的文章 如何理解二分查找？生活中还能用来设计骗局？ ，文章的末尾留下了两道题，本来是想问问小秋怎么做的，然而小秋今天去浪了，无法和你们讲解他的思路了。所以全程由帅地来和你们讲解。

1、求 x 的 n 次方

当然，这道题你也可以采用 n 次循环让 n 个 x 相乘，不过，这样的做法毫无意义，因为估计小学生也会做。

不过这道题如果知道了思路，还是挺简单，我举个例子吧，例如我们要求 2^8。

1、首先，我们可以通过 2 * 2 = 4 得到 2^2

2、接着，我们利用刚才的结果，让 4 * 4 = 16 得出 2^4

3、接着，同样的道理，让 16 * 16 = 256 得出 2^8

通过这种方法，只需要三次相乘即可得出，也就是说，我们可以在 O(logn) 的时间复杂度求出 x 的 n 次方。这种方法的思想，我们也称之为 快速幂思想 ，和二分查找的思想有点类型，每次都进行翻倍或者缩小一半。

这个时候有人可以能会问，如果 n = 8 或者 n = 16 ，由于 n 是 2 的幂次方，所以可以按照你上面的方法做，那如果 n = 12 呢？

其实道理是一样的，我们可以对 12 进行拆分啊，把 12 拆分成 12 = 4 + 8 就可以了。然后就有 2^12 = 2^4 * 2^8。

那如果 n = 13 呢，也是一样的，拆分成 13 = 1 + 4 + 8，即 2^13 = 2^1 * 2^4 * 2^8。

也就是说， 任何整数，都可以把它拆分成若干个 2 的幂次方进行相加。

代码如下

// 为了代码短一段，这里假设 n 是非负整数，并且不会产生溢出
int pow(int x, int n){
    int res = 1;
    while(n > 0){
        if(n % 2 == 1){
            res *= x;
        }
        n >> 1;
        x = x * x;
    }
}
复制代码

好吧，上篇文章中，我说不可以使用位运算，上面的代码还是用到了位运算，如果不使用的话，代码会比较复杂，这里跟各位说声不好意思，如果你对里面的代码看的不是很懂，说明你的牛逼的位运算不熟悉，可以看我之前的文章： 【算法技巧】位运算装逼指南

2、搜索旋转 排序 数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值 target，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
复制代码

解答

为了方便讲解，这里我们把数组中的最小值称之为 旋转点 吧。接下来我们就以上面中的例子来进行讲解。

没有旋转之前的数组

旋转之后的数组

显然，这个旋转点是 最特殊的点 ，因为旋转点既比左边的数小，同时也比右边的数小。

我们知道，在我们 平时的二分查找中 （也就是数组没有旋转之前），我们会把目标值 target 与 中间元素 mid 进行比较，每次比较都会有一下三种结果

（1）如果 target 比 mid 小，那么 mid 以及 mid 右边的所有元素一定比 target 大，所以 target 只能存在于 mid 的左边元素中。

（2）如果 target 比 mid 大，那么 mid 以及 mid 左边的所有元素一定比 target 小，所以 target 只能存在于 mid 的右边元素中。

（3）如果 target 与 mid 相等，则直接把 mid 对应的下标返回即可。

而在这道题中，情况要比这个复杂，因为它还有受 旋转点 的位置所影响，具体可以分为以下两种情况。

这里我在强调一下，二分查找的结果就是要把范围缩小一般，所以我们的目的就是， 寻找出 target 究竟是位于 mid 的左边还是右边。

（一）情况1：中间元素在旋转点的左侧

（1）target 在 mid 的左边。

。

（2）taeget 在 mid 的右边

如果不满足（1）的条件，则意味着在右边

（二）情况2：中间元素在旋转点的右侧或者和旋转点重合

右侧

重合

（1）target 在 mid 的 右边

显然，需要满足的条件是 mid < target <= 最右侧元素

（1）target 在 mid 的左边

如果不满足 (1) 中的条件，则在左边。

当然，在上面的情况中，我们没有 mid 与 target 相等的情况，因为如果他们相等的话，就直接返回下边即可，无需讨论。

上面的各种情况我们都讨论好了，下面我们直接按照上面的逻辑来写代码即可，代码如下：

int rotatedBinarySearch(int[] arr, int target){
    // 最左侧元素下标
    int left = 0;
    // 最右侧元素下标
    int right = arr.length - 1;
    while(left <= right){
        // 中间元素下标
        int mid = left + (right - left) / 2;
        if(arr[mid] == target){
            return mid;
        }
        
        // 情况1：如果中间元素在旋转点左侧
        if(arr[mid] >= arr[left]){
            //target 如果位于中间元素的左侧
            if(arr[mid] > target && target >= arr[left]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        // 情况2：中间元素在旋转点的右侧
        else{
            // target 如果位于中间元素的右侧
            if(arr[mid] < target && target <= arr[right]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
    }
    return -1;
}
复制代码

最后

对于有些需要分很多种情况讨论的题，说时候，不是很好讲，就算我详细着给你们讲，还是容易把你们给绕晕，所以在以后的选题中，我会尽量选择一些典型的，一道题能够引申出某个重点知识点的题来讲，当然，也欢迎大家给我提供一些有意思的题。

如果你觉得这篇内容对你挺有启发，为了让更多的人看到这篇文章：不妨

1、 点赞 ，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）

2、 关注我和专栏 ，让我们成为长期关系

3、关注公众号「 苦逼的码农 」，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章

大部分的数据结构与算法文章被各种公众号转载相信一定能让你有所收获

，第一时间阅读我的文章。