给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。 如果数组中不存在该元素，则返回 -1 -1。 输入格式 第一行包含整数 n 和 q，表示数组长度和询问个数。 第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。 接下来 q 行，每行包含一个整数 k，表示一个询问元素。 输出格式 共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。

答案：对于给定的数组和查询，可以使用二分搜索法来找到所求元素的起始位置和终止位置。具体步骤如下：1、先使用二分搜索法找到目标元素 k，如果不存在则返回 -1 -1；2、然后以 k 为中心，向左右两边搜索，直到找到最左边的位置和最右边的位置，返回其位置即可。

相关问题

**题目描述**： 实现归并排序算法，对给定的整数数组进行排序。 **输入**： - 一个未排序的整数数组 `arr` - 数组的长度 `n` **输出**： - 按升序排列的数组

归并排序是一种经典的排序算法，它采用分治的思想来实现。具体步骤如下：

1. 将数组分成两个子数组，直到每个子数组只有一个元素。
2. 对每个子数组进行排序，可以使用递归来实现。
3. 合并两个已排序的子数组，得到一个更大的已排序数组。
4. 重复步骤3，直到所有子数组都合并为一个完整的已排序数组。

以下是归并排序算法的实现代码：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    while i < len(left):
        result.append(left[i])
        i += 1
    
    while j < len(right):
        result.append(right[j])
        j += 1
    
    return result

对于给定的未排序整数数组 `arr`，可以调用 `merge_sort(arr)` 函数来进行排序。最终返回的结果就是按升序排列的数组。

用C语言，给定若干不同的整数构成的升序序列，请编写一个程序，找出序列中有多少个数是序列中其他两个数的平均值。 输入有多组测试样例。 每组测试样例的第一行为一个整数n( 3 ≤ n ≤ 1000 ) 。 第二行为 n 个不同的正整数，为该序列中的各个元素。所有的元素以升序排列，保证每个元素不超过10^9。对每组测试样例，请在单独的行中输出所求的结果。

以下是C语言的代码实现：

#include <stdio.h>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) { // 多组测试数据
        int arr[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }

        int count = 0;
        for (int i = 0; i < n; i++) { // 枚举所有数
            int left = 0, right = n - 1;
            while (left < right) { // 用双指针查找平均数
                int average = (arr[left] + arr[right]) / 2;
                if (average == arr[i]) { // 如果找到了平均数
                    count++;
                    break;
                } else if (average < arr[i]) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        printf("%d\n", count); // 输出答案
    }
    return 0;
}

首先，我们使用 `while` 循环读入多组测试数据，每一组数据包含一个整数 `n` 和一个长度为 `n` 的升序序列 `arr`。

接下来，我们使用双指针法枚举所有的数 `arr[i]`，并用双指针 `left` 和 `right` 查找平均数 `(arr[left] + arr[right]) / 2` 是否等于 `arr[i]`。如果找到了平均数，则计数器 `count` 加一。

最后，我们输出计数器 `count` 的值作为答案。

时间复杂度为 $O(n^2)$，可以通过此题。