折半查找之范围查找

题目描述

利用折半查找算法进行范围查找。所谓范围查找是要找出在给定值 $a$ 和 $b$ 之间的所有元素 $(a\leq b)$ 。

输入格式

（1）第1行是序列中的元素个数

（2）第2行是有序序列（数与数之间用空格分隔）

（3）第3行是下限和上限（用空格分隔）

输出格式

指定范围内的所有元素（数与数之间用空格分隔）

示例

输入（Input）：

8

1 3 4 6 7 8 9 15

5 10

输出（Output）：

6 7 8 9

代码

#include <iostream>
#include <stack>
using namespace std;

const int MAX_SIZE = 100;

void find(int min, int max, int r[MAX_SIZE], int low, int high) {
    int mid = (low + high) / 2;
    if(r[mid] < min) { // 分治求解左侧范围
        find(min, max, r, mid, high);
    }
    else if (r[mid] > max) { // 分治求解右侧范围
        find(min, max, r, low, mid);
    }
    else { // 输出答案
        stack<int> s; // 利用栈将mid左侧数按原来数组的顺序输出
        for(int i = mid; r[i] >= min && i >= low; i--) 
            s.push(r[i]);
        while(!s.empty()) {
            printf("%d ",s.top());
            s.pop();
        }
        for(int j = mid + 1; r[j] <= max && j <= high; j++)
            printf("%d ", r[j]);
    }
}

int main() {
	int n;    cin >> n; // 输入元素个数
	int r[MAX_SIZE];
	for(int i = 0; i < n; i++)    cin >> r[i];
	int a, b;    cin >> a >> b; // 输入查找范围的最小值和最大值
	find(a, b, r, 0, n);
	return 0;
}