旋转数组（二分查找）

1.旋转数组（189 - 中）

题目描述：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。进阶：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 :

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

思路：多解法，其中使用额外数组，空间复杂度O(N)，其余O(1)。

• 使用额外数组：遍历原数组，将原数组下标为 ii 的元素放至新数组下标为 (i+k)%n 的位置，最后将新数组拷贝至原数组即可。
• 模拟循环：用一个变量tmp维护移动k次，注意移动数组时倒序进行填充，防止覆盖，时间复杂度O(kn)，但是超时。
• 数组翻转：比较巧妙，先整体翻转，在将0 ~ k - 1和k - 1 ~ n - 1进行翻转。

代码实现：

class Solution {
    // 使用辅助数组
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] tmp = new int[n];
        
        for (int i = 0; i < n; i++) {
            tmp[(i + k) % n] = nums[i];
        }
        System.arraycopy(tmp, 0, nums, 0, n);
    }

    // 模拟移动（超时！）
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;

        for (int i = 0; i < k; i++) {
            int temp = nums[n - 1];
            for (int j = n - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }
    }

    // 数组翻转（先整体翻转，再翻转部分）
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
}

2.寻找旋转排序数组中的最小值（153 - 中）

题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。请你找出并返回数组中的 最小元素 。

示例 :

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

思路：本题可以直接遍历获取最小值，但是考察点二分查找。注意体会二分查找的思想，不要背模板，这里可以画个折线看看。

注：代码中比较元素取数组最后一个元素，也可以取任意一个元素。

代码实现：

public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] > nums[r]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return nums[l];
}

3.寻找旋转排序数组中的最小值II（154 - 难）

题目描述：整数数组 nums 按升序排列，数组中的值 可能存在重复值 。返回数组中的 最小元素 。同 剑指 Offer 11. 旋转数组的最小数字

示例 :

输入：nums = [2,2,2,0,1]
输出：0

思路：本题可以直接遍历获取最小值，但是考察点二分查找，与上题不同的是数组中可能含有重复值，但是二分的本质是二段性，并非单调性，所以我们还以使用二分。但时间复杂度可能退化O(n)，即全部是一种元素。

注意：由于重复元素的存在，我们并不能确定 nums[mid]究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 nums[r] 是不是最小值，都有一个它的「替代品」nums[mid]，因此我们可以忽略二分查找区间的右端点。

代码实现：

public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] > nums[r]) {
            l = mid + 1;
        } else if (nums[mid] < nums[r]){
            r = mid;
        } else {
            r--;
        }
    }
    return nums[l];
}

4.搜索旋转排序数组（33 - 中）

题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 :

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

思路：本题考查二分查找，但是二分查找要求数组有序，关键：

• 先通过mid和nums[r]（任意元素）比较确定有序区间在mid左边还是右边, 如T153
• 再确定目标元素target在哪边!，这时我们就可以直接根据target位置进行二分查找了。

代码实现：

class Solution {
    // 直接搜索
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    // 二分查找
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == target) return mid;
            if (nums[mid] > nums[r]) {
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

5.搜索旋转排序数组II（81 - 中）

题目描述：整数数组 nums 按升序排列（单调不减），数组中的值 可能存在重复值 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 :

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

思路：经过上述各题的过度，直接使用二分解法。与33题基本相同。不同的是含有重复元素。

时间复杂度：对于这种含重复元素的二分查找问题，最坏时间复杂度O(n)，即整个数组都是同一个数，最好时间复杂度O(nlogn)。

代码实现：

public boolean search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == target) return true;
        if (nums[mid] > nums[r]) {
            if (target >= nums[l] && target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else if (nums[mid] < nums[r]) {
            if (target > nums[mid] && target <= nums[r]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        } else {
            r--;
        }
    }
    return false;
}

6.在排序数组中查找目标值的首尾元素的索引（34 - 中）

题目描述：给定一个按照升序排列的整数数组 nums，可能含有重复值，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

要求：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 :

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路：代码1在极端情况下，时间复杂度退化为O(n)，不符合要求，但容易理解，实现简单。

其实，我们只需要找两个索引即可，大于target - 1的索引（即目标值的起始索引）和第一个大于target的数的索引 - 1，时间复杂度O(nlogn)，只调用了两次二分查找。

代码实现：

// 代码1
public int[] searchRange(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == target) {
            int start = mid, end = mid;
            while (start >= 0 && nums[start] == target) start--;
            while (end < n && nums[end] == target) end++;
            return new int[] {start + 1, end - 1}; 
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return new int[] {-1, -1};
}

// 代码2
public int[] searchRange(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    int leftIdx = binarySearch(nums, target - 1);
    int rightIdex = binarySearch(nums, target) - 1;
    if (leftIdx <= rightIdex && nums[leftIdx] == target && nums[rightIdex] == target) {
        return new int[] {leftIdx, rightIdex};
    }
    return new int[] {-1, -1};
}
// 返回大于target的第一个索引值
public int binarySearch(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1, ans = nums.length;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] > target) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

7.面试题：10.03（补充）

题目描述：返回目标元素的第一个索引，即索引值最小的那个（如果存在），不存在返回-1。

示例 :

 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 输出: 8（元素5在该数组中的索引）

思路：本题是T82和T34的思路的融合，但注意由于数组是经过旋转，所以不能像T34查找边界。类似这种情况旋转数组：[5,5,5,1,2,3,4,5] 目标值：5，返回的是7，却不是0。

• 如果左边索引满足条件，直接返回
• 二分，mid符合，但是我们找最小的，所以要更新右边界。
• mid不符合，找升序区间继续二分

代码实现：

public int search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l <= r) {
        if (nums[l] == target) return l;
        int mid = l + ((r - l) >> 1);
        // 索引mid的值是目标值（左边可能还有更小的索引值），更新右边界
        if (nums[mid] == target) r = mid;
        if (nums[mid] > nums[l]) {
            if (target >= nums[l] && target <= nums[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        } else if (nums[mid] < nums[l]) {
            if (target >= nums[mid] && target <= nums[r]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        } else {
            l++;
        }
    }
    return -1;
}

8.山脉数组的峰顶索引（852 - 易）

题目描述：符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在 i（0 < i < arr.length - 1）使得：
  arr[0] < arr[1] < ... arr[i-1] < arr[i]
  arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

示例 :

输入：arr = [0,2,1,0]
输出：1

思路：本题考察点二分查找，只不过二分的判断条件有点不同。即通过mid相邻点判断最大值所在区间。

代码实现：

public int peakIndexInMountainArray(int[] arr) {
    int n = arr.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (arr[mid] < arr[mid + 1]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

9.山脉数组中查找目标值（1095 - 难）

题目描述：给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。

示例 :

输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

思路：上一题的升级，我们寻找包含重复元素的最小索引值。类比面试题10.03。两阶段：

• 找到最大值索引，T852
• 分别在升序和降序区间找目标值。

时间复杂度O(nlogn)，进行三次二分查找（也可能两次）。

代码实现：

public int findInMountainArray(int target, MountainArray mountainArr) {
    // 1.查找峰顶索引
    int n = mountainArr.length();
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    // 2.对升序和降序数组分别进行二分查找(用flag标识升序和降序区间)
    int idx = binarySearch(target, mountainArr, 0, l, true);
    return idx != -1 ? idx : binarySearch(target, mountainArr, l + 1, n - 1, false);
}

public int binarySearch(int target, MountainArray mountainArr, int l, int r, boolean flag) {
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (mountainArr.get(mid) == target) return mid;
        if (mountainArr.get(mid) < target) {
            l = flag ? mid + 1 : l;  
            r = flag ? r : mid - 1;
        } else {
            r = flag ? mid - 1 : r;
            l = flag ? l : mid + 1;
        }
    }
    return -1;
}

10.两数相除（29 - 中）

思路：由于题目限定了我们不能使用乘法、除法和 mod 运算符。

核心：我们可以先实现一个「倍增乘法」，然后利用对于 x 除以 y，结果 x / y 必然落在范围 [0, x] 的规律进行二分。

注意：long mid = l + r + 1 >> 1，之前的用法会超时？

public int divide(int a, int b) {
    long x = a, y = b;
    boolean isNeg = (x < 0 && y > 0) || (x > 0 && y < 0);
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    long l = 0, r = x;
    while (l < r) {
        long mid = l + r + 1 >> 1;
        if (mul(mid, y) <= x) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    long ans = isNeg ? -l : l;
    if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) return Integer.MAX_VALUE;
    return (int)ans;
}
// 倍乘函数
public long mul(long a, long k) {
    long ans = 0;
    while (k > 0) {
        if ((k & 1) == 1) ans += a;
        k >>= 1;
        a += a;
    }
    return ans;
}

巨人的肩膀： @甜姨 @宫水三叶