789. 数的范围(二分模板)

Problem: 789. 数的范围

思路

这是一个二分查找的问题，我们需要找到数组中等于给定值的最左边和最右边的元素的位置。我们可以使用两次二分查找来解决这个问题，一次查找最左边的元素，一次查找最右边的元素。

解题方法

1.对于查找最左边的元素，我们初始化左边界为0，右边界为数组长度减1。然后进行二分查找，如果中间元素大于等于目标值，我们就将右边界移动到中间位置，否则将左边界移动到中间位置的右边。最后返回左边界的位置，如果该位置的元素不等于目标值，就返回-1。

2.对于查找最右边的元素，我们同样初始化左边界为0，右边界为数组长度减1。然后进行二分查找，如果中间元素小于等于目标值，我们就将左边界移动到中间位置，否则将右边界移动到中间位置的左边。最后返回左边界的位置，如果该位置的元素不等于目标值，就返回-1。

复杂度

时间复杂度:

$O(logn)$，其中n是数组的长度。我们进行了两次二分查找，每次查找的时间复杂度都是$O(logn)$。

空间复杂度:

$O(1)$，我们只使用了常数个变量。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int MAXN = 100010;
	static int[] nums = new int[MAXN];
	static int n, q;
	public static void main(String[] args) throws IOException {
		n = nextInt();
		q = nextInt();
		for(int i = 0; i < n; i++) {
			nums[i] = nextInt();
		}
		while(q-- > 0) {
			int num = nextInt();
			out.println(findLeftmostEquals(num) + " " + findRightmostEquals(num));
		}
		out.flush();
		
	}
	private static int findLeftmostEquals(int num) {
		int l = 0, r = n - 1;
		while(l < r) {
			int m = (l + r) / 2;
			if(nums[m] >= num) {
				r = m;
			} else {
				l = m + 1;
			}
		}
		if(nums[l] != num) {
			return -1;
		}
		return l;
	}
	private static int findRightmostEquals(int num) {
		int l = 0, r = n - 1;
		while(l < r) {
			int m = (l + r + 1) / 2;
			if(nums[m] <= num) {
				l = m;
			} else {
				r = m - 1;
			}
		}
		if(nums[l] != num) {
			return -1;
		}
		return l;
	}
	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}