Какой лучший алгоритм, чтобы увидеть, если мой номер в массиве диапазонов?

Question

У меня есть 2-мерные массивы в php, содержащие диапазоны.например:

From.........To
---------------
125..........3957
4000.........5500
5217628......52198281
52272128.....52273151
523030528....523229183  

и т. д.

, и это очень длинный список.Теперь я хочу увидеть, находится ли число, данное пользователем, в диапазоне.например, номера 130, 4200, 52272933 находятся в моем диапазоне, а номера 1, 5600 - нет.

Конечно, я могу сосчитать все индексы и посмотреть, больше ли мой номер, чем первый, и меньше, чем второй элемент.но есть ли более быстрый алгоритм или более эффективный способ сделать это с помощью функции php?

добавлено позже

Он отсортирован.на самом деле это числа, созданные с помощью ip2long (), показывающие все IP-адреса страны.Я просто написал код для него:

$ips[1] = array (2,20,100);
$ips[2] = array (10,30,200);
$n=11;// input ip
$count = count($ips);
for ($i = 0; $i <= $count; $i++) {
    if ($n>=$ips[1][$i]){
        if  ($n<=$ips[2][$i]){
            echo "$i found";
            break;
        }
    }else if($n<$ips[1][$i]){echo "not found";break;}
}

в этой ситуации числа 2,8,22 и 200 находятся в диапазоне.но не цифры 1,11,300

Answer 1

Поместите диапазоны в плоский массив, отсортированный по убыванию, как показано ниже:

a[0] = 125
a[1] = 3957
a[2] = 4000
a[3] = 5500
a[4] = 5217628
a[5] = 52198281
a[6] = 52272128
a[7] = 52273151
a[8] = 523030528
a[9] = 523229183

Затем выполните бинарный поиск, чтобы определить, по какому индексу этого массива должно быть вставлено соответствующее число.Если индекс вставки четный, то число не входит ни в один поддиапазон.Если индекс вставки нечетный, то число попадает в один из диапазонов.

Примеры:

n = 20  inserts at index 0 ==> not in a range
n = 126 inserts at index 1 ==> within a range
n = 523030529 inserts at index 9 ==> within a range

Answer 2

Вы можете ускорить процесс, реализовав алгоритм двоичного поиска .Таким образом, вам не нужно смотреть на каждый диапазон.Затем вы можете использовать in_array, чтобы проверить, находится ли число в массиве.

Я не уверен, правильно ли я вас понял, действительно ли ваши массивы выглядят так:

array(125, 126, 127, ..., 3957);

Если так, какой смысл?Почему бы просто не иметь?

array(125, 3957);

Это содержит всю необходимую информацию.

Answer 3

В приведенном вами примере предполагается, что числа могут быть большими, а пространство - сравнительно небольшим.

В этот момент у вас не так много вариантов. Если массив отсортирован, бинарный поиск - это почти все, что есть. Если массив не отсортирован, вы переходите к простому старому линейному поиску CS101.

Answer 4

Правильная структура данных для этой проблемы - дерево интервалов .Как правило, это намного быстрее, чем бинарный поиск.

Answer 5

С прагматической точки зрения линейный поиск вполне может оказаться самым быстрым методом поиска. Подумайте об ошибках страницы и времени поиска жесткого диска здесь.

Если ваш массив достаточно большой (что на самом деле означает «достаточно»), возможно, было бы целесообразно поместить ваши IP-адреса в базу данных SQL и позволить базе данных выяснить, как эффективно вычислять SELECT ID FROM ip_numbers WHERE x BETWEEN start AND end;.

Answer 6

Я предполагаю, что диапазоны не перекрываются.

Если это так, вы можете сохранить структуру данных карты, которая указана на более низком значении диапазона.

Теперь все, что вам нужно сделать (учитывая число N), это найти ключ на карте, который чуть ниже N (используя двоичный поиск - логарифмическая сложность), а затем проверить, меньше ли число, чем правильное значение.

По сути, это бинарный поиск (логарифмический) на построенной карте.