假定有一组N的范围，（A1，B1）（A2，B2）（A3，B3）...（安，BN），其中艾表示起点和Bi表示的终点范围。 （艾毕是正整数）

Suppose we have a set of N ranges, (A1, B1) (A2, B2) (A3, B3) ... (An, Bn), where Ai denotes the starting point and Bi denotes the ending point of a range. (Ai, Bi are positive integers)

我们如何检查是否使用了二进制搜索做的，如果给定的整数，比如X，存在至少一个的N范围？

How do we check using Binary Search if the given integer, say X, exists in at least one of the N ranges?

我的方法：

排序范围由x坐标，然后再由y坐标。

Sort the ranges by x-coordinate first and then by y-coordinate.

查找最小的x坐标大于或等于X。

Find the smallest x-coordinate greater or equal to X.

检查的范围是满意的。

如果是的，我们有一个解决方案。

If yes, we have a solution.

现在，如果范围犯规包含X，应该是我的下一个步骤？

Now, if that range doesnt contain X, what should be my next step?

或者，如果解决方案是完全不同的？

Or, should the solution be entirely different?

推荐答案

首先，如果范围不排序，你最好检查一个接一个，而不是做任何花哨的二进制搜索，因为检查每范围将最多为O（n），而排序，然后二分查找将至少为O（n log n）的。

First of all, if the ranges aren't sorted, you're better off checking one by one instead of doing any fancy binary search, because checking each range will be at most O(n), whereas sorting and then binary searching will be at least O(n log n).

不管怎样，在这种情况下，我会考虑所有与范围相同的x坐标是一个单一的节点，所以当你二进制搜索，中间节点，你实际上是在组内具有范围相同的x坐标。然后你会检查最后在范围内该节点的y坐标。如果该号码不是这两个之间，则该号码不包含在任何的节点的范围的，所以应该要么去向左或向右取决于数是否比更高或更低x或y坐标。

Anyway, in this case I'd consider all the ranges with the same x-coordinate to be a single node, so when you're binary-searching, the middle node you get will actually be the group of ranges that have the same x-coordinate. You'd then check the y-coordinate of the last range in that node. If the number is not between those two, then the number is not contained in any of the ranges of that node, so you should either go left or right depending on whether the number is higher or lower than the x or y-coordinates.

下面是用Python全面工作的例子：

Here's a full working example in Python:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random
import itertools

MAX = 50
NUM_RANGES = 30

THE_NUMBER = random.randint(0, MAX)

ranges = []
# Generate random ranges
for e in range(NUM_RANGES):
    x = random.randint(0, MAX - 1)
    y = random.randint(x + 1, MAX)

    ranges.append((x,y))

# Group the ranges by starting coordinate
grouped_ranges = {x: [e for e in ranges if e[0] == x] for x in (e[0] for e in ranges)}

## Binary search
gkeys = grouped_ranges.keys()
gkeys_range = [0, len(gkeys)]

get_mid_key = lambda: (gkeys_range[1] + gkeys_range[0])/2
get_mid = lambda: grouped_ranges[gkeys[get_mid_key()]]

print "THE NUMBER:", THE_NUMBER
print "THE RANGES:", grouped_ranges

while 1:
    # Get middle element
    mid = get_mid()

    print gkeys_range

    old_range = gkeys_range[:]

    if THE_NUMBER < mid[0][0]:
        gkeys_range[1] = get_mid_key()
    elif THE_NUMBER > mid[-1][1]:
        gkeys_range[0] = get_mid_key()
    else:
        print "In this range:", mid
        break

    if gkeys_range == old_range:
        print "Not in any range"
        break