Лучший способ найти значение в списке, когда список отсортирован

Question

Допустим, у меня есть Java ArrayList, который отсортирован. Теперь я хотел бы найти индекс значения х. Какой самый быстрый (без более чем 30 строк кода) способ сделать это? Использование метода IndexOf ()? Перебирать все значения в простом цикле for? Использовать какой-нибудь крутой алгоритм? Мы говорим примерно о 50 целочисленных ключах.

Answer 1

Двоичный поиск , но разве это всего лишь 50 пунктов, кого это волнует (если вам не придется делать это миллионы раз)? Простой линейный поиск проще, а разница в производительности для 50 наименований незначительна.

Редактировать : Вы также можете использовать встроенный метод java.util.Collections binarySearch . Имейте в виду, что он вернет точку вставки, даже если элемент не найден. Возможно, вам придется выполнить дополнительную пару проверок, чтобы убедиться, что товар действительно тот, который вам нужен. Спасибо @Matthew за указатель.

Answer 2

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

Тем не менее, Java имеет встроенную функциональность для двоичного поиска по спискам (включая ArrayLists), Collections.binarySearch .

Answer 3

import java.util.ArrayList;
import java.util.Collections;

ArrayList myList = new ArrayList();
// ...fill with values

Collections.sort( myList );
int index = Collections.binarySearch( myList, "searchVal" );

Редактировать: непроверенный код

Answer 4

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

Учитывая время кодирования IndexOf() - это путь (или встроенный двоичный поиск, если он доступен для вашего типа данных (я из C # и не знаю Java)).