Привет, всем!
Подскажите, пожалуйста, как организовать поиск в упорядоченном массиве длиной, допустим, 1000000000000.
В принципе длина не важна. Суть в том, что она больше чем позволяет long int. Как можно поступить в таком случае?

Бинарный поиск это логорифмическое время.
2^100 = 1 267 650 600 228 229 401 496 703 205 376 
Всего 100 итераций. 

Это больше чем влазит в int64.

Добавлено через 2 минуты
Это пожалуй больше чем емкость всех жестких дисков которые были произведены на свете.

хм... очень странно. потому что меня сегодня на собеседовании попросили провести поиск в таком массиве =) ну можт я на пару нулей ошибся...

если уж массив отсортирован - однозначно двоичный (бинарный) поиск. 

Проблема не в том, как искать в таком массиве, а где его хранить   В память (32х битную) он не влезет, т.е. хранить надо на внешнем носителе, и искать там же.
Т.е. вопрос превращыется в другой - как организовать бинарный поиск в (большом) файле на диске.

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

Если известен формат хранения файла и есть интерфейс доступа, то в прицнипе какие проблемы? 

Хэш таблицу сначала надо построить   По моему, эдесь было произнесено 3 ключевые фразы:

•  упорядоченный массив
•  длинна массива больше чем позволяет long int
•  на собеседовании попросили

Так что выводы:

•  Бинарный поиск
•  Внешнее хранилище
•  Законченное работающее решение не требуется - надо только показать алгоритм решения

1000000000000
32 бита
4294967296
64 бита
18446744073709551616
то есть вполне можно работать

тера гига мега кило
1000'000'000'000
опять же не уточняю окончания, впрочем учитывая как врут современные производители винтов, используя 1000 вместо 1024 и меняя там стандартные системы как вздумается (кстати я по старому считаю и плевал на то, что они там протащили за свои деньги), в общем учитывая это, винты вполне тоже способны хранить такой массив.

А дальше двоичный поиск. Делим адресацию на два и проверяем условие сравнения.
найти 3 (деление без округления, с отбрасыванием остатка)
01234 56789
01 234
2 34
3 4
3

B tree
B+ tree

я так понимаю это относилось к фразе 


но там говорилось не о 

а о

mes, я как бы определил область эффективности алгоритма. Т.е. сто итераций это верхний предел того что может понадобиться. Раз это производиться быстро даже для невообразимо большого объема данных, то тем более быстро в всех остальных случаях.

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

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

Добавлено через 1 минуту и 38 секунд



Это сообщение отредактировал(а) mes - 3.2.2010, 12:51

А я бы спросил про память и задачу: надо найти быстро или находить быстро (несколько раз).
Если "памяти мало и находить несколько раз", то вероятно с ходу бы я разбил бы массив на N частей, и зная границы (значения на них) частей искал бы уже в частях (массив, напомню, сортированный). Индексация массива таким образом очень быстра, а выигрышь в скорости поиска может быть значительным (считать лениво). И это будет быстрее бинарного поиска (возможно, не при одиночном проходе) и не жрать столько памяти , сколько хеш таблицы или деревья....

Это сообщение отредактировал(а) jonie - 4.2.2010, 02:23