查找

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

Data Structures Experiment #14 - 查找

Puzzle 1

给定一个包含n个数字的有序数组，每次查询数组中大于等于数字q的第一个元素。保证q小于等于最大元素。

输入：

第一行包含两个数字：n，Q，表示数组中元素个数和查询个数。第二行包含n个数字，表示有序数组。接下来Q行每行一个整数q，表示询问元素。（$n\le 10^{6}$，$q\le 10^{5}$）

输出：

对于每个查询q，输出查询结果。

输入样例:

1
2
3
4
5
5 3
10 20 30 40 50
2
49
50

输出样例:

1
2
3
10
50
50

目的是在一个有序数组中找到第一个不小于q的数。

最简单的方法是顺序查找，第一个找到的不小于q的数就是要输出的数。

但是此种方法的平均查找长度较大，当表长较大时不太适用。

注意到数组是有序的，所以可以采用折半查找的方式。类似于“二分法”，每次将待查区间缩小一半，缩到最小时便找到了要查找的数值。

对应题目中的变量名称声明变量，读取数组长度、查找次数和数组。

对于每次查找，先置三个“指针”low、mid和high指向表头、表中和表尾。并比较mid处的值arr[mid]和要查找的值q的大小：

  • 非常幸运，若arr[mid]等于q，mid之前除了可能的若干个等于q的数之外，一定全都小于q。所以arr[mid]就是我们要找的“第一个”不小于q的数（真正的“第一个”一定与其相等），跳出循环。
  • 一般情况，若arr[mid]不等于q：
    • 如果mid位置的数比q小，说明q的范围一定在mid的后半段，且此时arr[mid]一定不可能满足要求，故移动low并指向mid的后一个位置，并跟随移动mid；
    • 如果mid位置的数比q大，说明q的范围一定在mid的前半段，但此时arr[mid]可能满足要求，故移动high并指向mid，并跟随移动mid。

经过若干次移动和比较，最终会出现两种情况之一跳出了循环：

  • 某次mid处的值arr[mid]等于q跳出循环；
  • high与low重合。

造成这两种情况的原因都是mid逐渐逼近q，最终指向不小于q的第一个数值（或与其相等的数值）。

即此时mid指向的值就是要输出的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;

int main()
{
    int n, Q, i, q;
    int low, high, mid;
    cin >> n >> Q;
    int *arr = new int[1000000];
    for (i = 0; i < n; i++)
        cin >> arr[i];
    for (i = 0; i < Q; i++) {
        cin >> q;
        low = 0;
        high = n - 1;
        mid = (n - 1) / 2;
        while (low < high) {
            if (arr[mid] == q)
                break;
            else if (arr[mid] < q)
                low = mid + 1;
            else if (arr[mid] > q)
                high = mid - 1;
            mid = (low + high) / 2;
        }
        cout << arr[mid] << endl;
    }
    delete[] arr;
    return 0;
}

Puzzle 2

现在有n个（$n\le 1000$）小木棍，每个小木棍的长度为$len_{i}$（$len_{i}\le 10^{9}$）。从n个木棍中拿出3个，计算多少种取法可以使得三个木棍组成三角形？

输入：

第一行包含一个整数n，第二行包含n个整数，表示木棍长度。

输出：

输出一个整数，表示可组成三角形的取法。

输入样例1：

1
2
5
10 20 20 20 30

输出样例1：

1
7

输入样例2：

1
2
5
20 20 20 30 20

输出样例2：

1
10

判断三边能否构成三角形，只需满足两条较小边之和大于第三边，此时任意两边均大于第三边。

但是如何有序地取三条边且找到较小边而又保证不重复？

由于需要判断边的大小，首先应将未知顺序的数组进行排序。

我们将三角形的三条边分成了较小的两条和最长的一条，所以可以以较小两边为基准或以最长边为基准进行查找与判断。当然，以一条边为基准要比以两条边为基准进行查找判断更为简便。

因为这条基准边是三条边里最长的，而且数组已经按升序排好，所以应从数组最大值处（len[n-1]）开始查找。

已经确定了最长边的位置，那么如何确定两条较小边的位置？

可能会想，最长边是从最大值开始的，较小边就应从最小值和次小值开始。但是要注意，我们判断的是“两条较小边之和大于第三边”，所以应该让这两条边一开始就满足“之和大于第三边”更好，可以避免“之和小于第三边”的情况。

但是是不是这两条边取倒数第二位和倒数第三位更好呢？还是要注意我们的目的——判断“两条较小边之和大于第三边”，所以两边之和应该均匀变化，才能准确找到两边之和的临界值，小于此值的情况则无需考虑。

对比两条边同时变化与一次只变化一条边，不难看出后者导致之和的变化更均匀。从上一道题中我们得到启发，即查找时应从中间值开始，比从最小到最大（或最大到最小）更为高效。

当最长边取到len[i]时：

  • 两边之和的最小值是两边分别取len[0]和len[1]时；
  • 两边之和的最大值是两边分别取len[i-2]和len[i-1]时；
  • 而两边之和的“中位数”是两边分别取len[0]和len[i-1]时（此时虽然不一定是“中位数”，但这样选择更便于操作）。

这样我们确定了最长边的位置，以及相对应的两条较小边的起始位置。接下来即进行和的判断：

  • 若此时两较小边之和比第三边小，则只需将最小边取到数组的下一个元素使和增大，继续判断；

  • 若此时两较小边之和比第三边大，这正是我们想要的结果。假设此时最小边位于p处，次小边位于q处，最长边位于r处，我们可以发现，不仅p、q和r可以构成三角形，而且当最小边取p～q-1之间任一值时都满足判断条件（此时用“最小边”是因为稍后“次小边”会变化）。即p～q-1共计q-p种情况都可取。

    计数完毕后，将次小边取到数组的上一个元素使和增大，继续判断。

以此类推，和不足时最小边增大，和过剩时次小边减小，最终二者重合使和到达临界（有点类似趋于平衡）：

  • 临界之上是次小边的所有取值，且对于每种取值时最小边的所有情况均已计数；
  • 临界之下是所有不满足的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;

int main()
{
    int n, i;
    int count = 0;
    cin >> n;
    unsigned int* len = new unsigned int[1000];
    for (i = 0; i < n; i++)
        cin >> len[i];
    sort(len, len + n);
    for (int i = n - 1; i > 1; i--) {
        int low = 0, high = i - 1;
        while(low < high) {
            if (len[low] + len[high] > len[i]) {
                count += (high - low);
                high--;
            }
            else
                low++;
        }
    }
    cout << count << endl;
    delete[] len;
    return 0;
}