C ++ строковый массив бинарный поиск - PullRequest
Новая
       27

C ++ строковый массив бинарный поиск

4 голосов
/ 30 марта 2010 
string Haystack[] =  { "Alabama", "Alaska", "American Samoa", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "District of Columbia",
                 "Florida", "Georgia", "Guam", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
                 "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", 
                 "Nevada", "New Hampshire", "New Jersey", "New Mexico", "New York", "North Carolina", "North Dakota", "Northern Mariana Islands", "Ohio", "Oklahoma",
                 "Oregon", "Pennsylvania", "Puerto Rico",  "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "US Virgin Islands", "Utah",
                 "Vermont", "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"};

 string Needle = "Virginia";

 if(std::binary_search(Haystack, Haystack+56, Needle))
      cout<<"Found";

Если бы я также хотел найти расположение иглы в массиве струн, есть ли «простой» способ выяснить это?

Ответы [ 2 ]

5 голосов
/ 30 марта 2010

Из документов SGI :

Обратите внимание, что это не обязательно та информация, которая вас интересует! Обычно, если вы проверяете, присутствует ли элемент в диапазоне, вы хотите знать, где он находится (если он присутствует) или где он должен быть вставлен (если его нет). Функции lower_bound, upper_bound и equal_range предоставляют эту информацию.

Я думаю, что причина этого набора интерфейсов в том, что binary_search на самом деле не указывает, вернет ли он начало диапазона совпадений (при условии, что совпадения есть) или конец диапазона, и вы хотите один или другой в зависимости от того, хотите ли вы что-то сделать с данными, уже находящимися в контейнере, или добавить новый элемент (возможно, в конец соответствующего диапазона). Или вы можете захотеть передать весь диапазон чему-то другому. Отсюда различные более или менее конкретные интерфейсы для выполнения бинарного поиска.

К сожалению, вы вряд ли найдете другие, если будете думать: «Мне нужна процедура бинарного поиска».

0 голосов
/ 30 марта 2010

Я гуглил и нашел это http://www.cplusplus.com/reference/algorithm/binary_search/... Это может быть простой способ достичь вашей цели

...