【宫水三叶の真题精选】利用二段性进行二分找分割点

朴素做法

一个朴素的做法，从前往后进行处理，直到遇到符合条件的位置。

代码：

import java.util.*;

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

• 时间复杂度：
• 空间复杂度：

二分解法

利用数组本身有序，我们可以通过二分找插入位置。

具体的，通过二分找到符合 nums[mid] <= target 的分割点。注意二分完后需要再次检查是否位置是否符合条件，如果不符合，代表插入元素应该被添加到数组结尾。

代码：

import java.util.*;

public class Solution {
    public int search (int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return nums[r] == target ? r : -1;
    }
}

• 时间复杂度：
• 空间复杂度：

最后

这是我们「必考真题 の 精选」系列文章的第 No.160 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)