输入集

排序数组

以下题目均默认在非严格递增的数组上搜索，可以涵盖严格递增数组的情况。

（如果在非严格递减的数组上搜索，仅需把大于小于号取反，如>=变为<=，<=变为>=）

问题列表见右侧TOC目录：

在排序数组中查找数字

// in: nums[], target
int pos = searchFirst(0, nums.length - 1, (mid) -> nums[mid] >= target);
return nums[pos] == target? pos: -1;

在排序数组中查找数字第一个位置

// in: nums[], target
int pos = searchFirst(0, nums.length - 1, (mid) -> nums[mid] >= target);
return nums[pos] == target? pos: -1;

在排序数组中查找数字插入位置

查找数字插入位置，如果已经存在则返回位置

// in: nums[], target
// 不需要判断mid==nums.length的原因：searchFirst中mid向下取整，mid永远不会等于末尾
return searchFirst(0, nums.length, (mid) -> nums[mid] >= target);

在排序数组中查找数字末一个位置

// in: nums[], target
int pos = searchLast(0, nums.length - 1, (mid) -> nums[mid] <= target);
return nums[pos] == target? pos: -1;

在排序数组中查找数字的范围

// in: nums[], target
int first = searchFirst(0, nums.length - 1, (mid) -> nums[mid] >= target);
int last = searchLast(0, nums.length - 1, (mid) -> nums[mid] <= target);
return nums[first] != target? new int[]{-1, -1}: new int[]{first, last};

在排序数组中查找数字的个数

// in: nums[], target
int first = searchFirst(0, nums.length - 1, (mid) -> nums[mid] >= target);
int last = searchLast(0, nums.length - 1, (mid) -> nums[mid] <= target);
return nums[first] != target? 0: last - first + 1;

在排序矩阵中查找数字

// 排序矩阵，每一行从左往右递增，且下一行最小元素比上一行最大元素大
// 二维坐标转换一维坐标
// x, y -> x * m + y
// index -> x = index / m, y = index % m
boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 ||
        matrix[0] == null || matrix[0].length == 0) {
        return false;
    }
    int ans = searchFirst(0, n * m - 1, (mid) -> get(matrix, mid) >= target)
    
    return get(matrix, start) == target;
}

int get(int[][] matrix, int index) {
    int x = index / matrix[0].length;
    int y = index % matrix[0].length;
    return matrix[x][y];
}

转序数组

主要包括一些具有特殊排序性质的数组，如如下两种：

山脉数组

数组定义

山脉数组：如果数组 A 是一个山脉数组的话，那它满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

• A[0] < A[1] < ... A[i-1] < A[i]
• A[i] > A[i+1] > ... > A[A.length - 1]

不严格山脉数组，即所有的大于、小于均变为不严格的大于、小于

对于山脉数组，严格山脉数组和非严格的山脉数组都具有两段性（可以直接的判断在左右着右），如下提供一套统一的写法。

问题列表见右侧TOC目录：

山脉数组峰值

要求：找到一个山脉数组（可以是严格的也可以是不严格的）中峰值的索引

分析：即寻找第一个开始准备下降（比下一个元素大）的元素

public int peakIndexInMountainArray(int[] nums) {
    int n = nums.length;
    // 第一个符合mid > mid+1的，即第一个开始往下走的，即上坡的顶端
    return searchFirst(0, n - 1, 
        (mid) -> nums[mid] > nums[mid + 1]
    );
}

题号：lc162, 852

山脉数组搜索

要求：在山脉数组中寻找target的索引，如果不存在则返回-1

分析：先找到峰值的索引，然后左侧即为单调增的数组、右侧是单调减，然后分别在左右去搜索。

int findInMountainArray(int target, MountainArray nums) {
    int n = nums.length();
    // 寻找峰值，第一个一个符合mid > mid+1的，即上坡的末尾，下面就准备下坡了
    int peak = searchFirst(0, n - 1, 
        (mid) -> nums.get(mid) > nums.get(mid + 1)
    );
    // 搜索上坡
    int left = searchFirst(0, peak, (mid) -> nums.get(mid) >= target);
    if (nums.get(left) == target) {
        return left;
    }
    // 搜索下坡
    int right = searchFirst(peak, n - 1, (mid) -> nums.get(mid) <= target);
    if (nums.get(right) == target) {
        return right;
    }
    
    // 两边都没找到，则不存在
    return -1;
}

题号：1095

旋转排序数组

数组定义

原数组是单调递增/减的数组，然后经过未知步数k次的轮转（即末尾k个元素放到原数组的头部），形成旋转排序数组。

不严格旋转排序数组，即原数组变为不严格增/减

对于旋转排序数组，严格的直接具有两段性（可以直接的判断在左右着右），不严格的在最左侧和最右侧相等的时候，无法直接判断往左走还是往右走，所以对于不严格的旋转排序数组，需要恢复两段性：先遍历一遍消除最右侧与最左侧相同的元素，保证最右端的元素小于最左端（这样才可以判断左右）

问题列表见右侧TOC目录：

严格旋转排序数组的最小值

要求：找到一个严格旋转排序数组中最小值

分析：即寻找最靠左的比右边界小的元素（即找到的即未旋转部分的最开头的）

public int findMin(int[] nums) {
    int n = nums.length;
    // 即寻找最靠左的比有右边界小的元素
    int pos = searchFirst(0, n - 1, (mid) -> nums[mid] <= nums[n - 1]);
    return nums[pos];
}

题号：lc153

严格旋转排序数组的最大值

要求：找到一个严格旋转排序数组中最大值

分析：即寻找最靠右的比左界小的元素（即找到的即旋转部分的最右侧）

public int findMax(int[] nums) {
    int n = nums.length;
    // 即寻找最靠右的比有左界小的元素
    int pos = searchLast(0, n - 1, (mid) -> nums[mid] >= nums[0]);
    return nums[pos];
}

题号：lc153

严格旋转排序数组搜索

要求：找到一个严格旋转排序数组中值为target的元素，如果不存在则返回-1

分析：即寻找最靠右的比左界小的元素（即找到的即旋转部分的最右侧）

两次遍历写法：（推荐）

public int search(int[] nums, int target) {
    int n = nums.length;
    int max = searchLast(0, n - 1, (mid) -> nums[mid] >= nums[0]);
    int left = searchLast(0, max, (mid) -> nums[mid] <= target);
    if (nums[left] == target) {
        return left;
    }
    // 这里max相当于哨兵，可以防止越界
    // searchLast的时候开头元素不会被mid取到，如果后面条件都不符合才会返回头
    int right = searchLast(max, n - 1, (mid) -> nums[mid] <= target);
    return nums[right] == target? right: -1;
}

一次遍历写法：（不推荐，因为条件太复杂了）

public int search(int[] nums, int target) {
    int n = nums.length;
    // 即寻找最靠左的比有右界小的元素
    int pos =  searchFirst(0, n - 1, (mid) -> {
        if (nums[mid] < nums[n - 1]) {
            // 在右半部分
            if (nums[mid] >= target || target > nums[n - 1]) {
                // 若mid大于等于target，则在最低点和mid之间，往左找；
                // 若target > nums[n - 1]，则一定在左半侧，也需要往左找
                return true;
            }
        } else {
            // 在左半部分
            if (nums[0] <= target && target <= nums[mid]) {
                // target，在0和mid之间，则往mid左侧找
                return true;
            }
        }
        
        return false;
    });

    return nums[pos] == target? pos: -1;
}

题号：lc33

不严格旋转排序数组的最小值

与严格的类似，只是多了一步恢复两段性：

public int findMin(int[] nums) {
    int n = nums.length - 1;
    // 恢复两段性，保证最右端的元素小于最左端（这样才可以判断左右）
    while (0 < end && nums[end] == nums[0]) n--;
    int end = n;
    int pos = searchFirst(0, end, (mid) -> nums[mid] <= nums[finalEnd]);
    return nums[pos];
}

题号：lc154

不严格旋转排序数组的最大值

与严格的类似，只是多了一步恢复两段性：

public int findMax(int[] nums) {
    int left = 0, right = nums.length - 1;
    // 恢复两段性，保证最右端的元素小于最左端（这样才可以判断左右）
    while (left < right && nums[right] == nums[left]) right--;
    int pos = searchLast(left, right, (mid) -> nums[mid] >= nums[0]);
    return nums[pos];
}

题号：无lc原题，来自字节笔试题

不严格旋转排序数组搜索

与严格的类似，只是多了一步恢复两段性：

public boolean search(int[] nums, int target) {
    int n = nums.length;
    int end = n - 1;
    // 恢复两段性
    while (0 < end && nums[end] == nums[0]) end--;
    int max = searchLast(0, end, (mid) -> nums[mid] >= nums[0]);
    int left = searchLast(0, max, (mid) -> nums[mid] <= target);
    if (nums[left] == target) {
        return true;
    }
    // 这里max相当于哨兵，可以防止越界
    // （searchLast的时候开头元素不会被mid取到，如果后面条件都不符合才会返回头）
    int right = searchLast(max, end, (mid) -> nums[mid] <= target);
    return nums[right] == target;
}

题号：lc88