二分查找算法进阶：山脉数组与旋转排序

一、852.山脉数组的峰顶索引

题目链接：852.山脉数组的峰顶索引

题目解析：

• 给我们一个数组，元素是先递增在递减的，让我们返回最大元素下标。

1.1 二分查找

解题思路：

• 我们这个数组本来就是一个被天然分成两段，递增区间和递减区间，的数据，天然使用二分查找的题。
• 当 mid 的元素小于后一个元素的时候，mid 在递增区间，所以 left = mid + 1。
• 当 mid 的元素大于后一个元素的时候，mid 在递减区间，所以 right = mid。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

1.2 暴力枚举

解题思路：

• 直接使用 for 循环遍历数组，该下标元素大于前面和后面元素，返回下标。
• 因为这个数组一定是一个山脉数组，所以不用管数组头和尾。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                return i;
            }
        }
        return 0;
    }
}

二、162.寻找峰值

题目链接：162.寻找峰值

题目解析：

• 给我们的数组是，递增递减反复进行，让我们找到其中一个峰值的下标。
• 数组可能是这几个情况：1. ///\ ，2. / ，3. \

2.1 二分查找

解题思路：

• 其实我们可以将数组分为，有要求峰值和没有要求峰值两段，因为给了峰值不等于下一个元素。
• 所以当 mid 小于下一个元素的时候，mid 就是在没有要求峰值那段，left = mid+1。
• 当 mid 大于下一个元素的时候，mid 就是在有峰值那段，right = mid

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

2.2 暴力枚举

解题思路：

• 直接转变为求数组最大值下标，遍历数组即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int findPeakElement(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > nums[ret]) {
                ret = i;
            }
        }
        return ret;
    }
}

三、153.寻找旋转排序数组中的最小值

题目链接：153.寻找旋转排序数组中的最小值

题目解析：

• 数组旋转一次就代表将数组尾元素放在数组头。
• 给我们一个原来升序的数组，旋转多次后，找到数组中最小元素下标。
• 数组中元素各不相同。

数组会是下面这种状态或者一个完全递增的状态

3.1 二分查找

解题思路：

• 我们这个数组本来就是已经是被分成两段了的。
• 我们可以使用 nums[0] 或者 nums[nums.length - 1] 来当分界线。
• 使用 nums[nums.length - 1] 为界限：
  • mid 元素大于等于界限时，在数组段 1，所以 left = mid + 1。
  • mid 元素小于界限的时候，在数组段 2，所以 right = mid。
• 使用 nums[0] 为界限：
  • mid 元素大于等于界限时，在数组段 1，所以 left = mid + 1。
  • mid 元素小于界限的时候，在数组段 2，所以 right = mid。
• 考虑数组完全递增时，nums[0] 才是最小值。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
//使用 nums[ nums.length - 1 ] 为界限：
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[nums.length - 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

//使用 nums[ 0 ] 为界限：
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[0] < nums[left]) {
            left = 0;
        }
        return nums[left];
    }
}

3.2 暴力枚举

解题思路：

• 直接循环遍历数组找最小值即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int findMin(int[] nums) {
        int ret = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < ret) {
                ret = nums[i];
            }
        }
        return ret;
    }
}

四、LCR 173.点名

题目链接：LCR 173.点名

题目解析：

• 给你一个长度为 n 数组，这个数组中有 0 到 n 中的数，按升序排列，找出数组在 0 到 n 中不含有的数。

4.1 二分查找

解题思路：

• 这个数组分为这样两段，一段是下标与元素值相同的，一段是下标是元素值减 1。
• 所以当 mid 元素等于 mid 的时候，落在第一段，left = mid + 1;
• 当 mid 元素不等于 mid 的时候，落在第二段，right = mid。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

4.2 哈希表

解题思路：

• 借助一个数组来标记 0 到 n 中出现过的元素。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
    public int takeAttendance(int[] records) {
        int[] hash = new int[records.length + 1];
        for (int i = 0; i < records.length; i++) {
            hash[records[i]]++;
        }
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] == 0) {
                return i;
            }
        }
        return 0;
    }
}

4.3 暴力枚举

解题思路：

• 直接遍历数组，当出现第一个下标和元素不相等的直接返回元素减一即可。
• 遍历完数组还是没找到，证明是 0 到 n 中 n 不在数组中。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int takeAttendance(int[] records) {
        for (int i = 0; i < records.length; i++) {
            if (records[i] != i) {
                return records[i] - 1;
            }
        }
        return records.length;
    }
}

4.4 位运算

解题思路：

• 直接使用一个变量来将 0 到 n 的数全部异或。
• 在于数组元素进行异或。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int takeAttendance(int[] records) {
        int res = 0;
        int n = records.length;
        // 异或 0 到 n
        for (int i = 0; i <= n; i++) {
            res ^= i;
        }
        // 异或数组元素
        for (int x : records) {
            res ^= x;
        }
        return res;
    }
}

4.5 数学（求和）

解题思路：

• 直接先将 0 到 n 的和求出来。
• 在减去数组中的元素即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int takeAttendance(int[] records) {
        int n = records.length;
        int ret = (n * (n + 1)) / 2;
        for (int i = 0; i < records.length; i++) {
            ret = ret - records[i];
        }
        return ret;
    }
}