Binary search in an ordered list in java [closed]

Question

Im looking for a way to implement a code in java that works the same way as a binary search in an ordered ArrayList but for an ordered List Thanks

Answer 1

You can use

Collections.<T>binarySearch(List<T> list, T key)

for binary search on any List. It works on ArrayList and on LinkedList and on any other List.

However:

binary search is only fast if you have direct access to each element:

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

If your List does not provide "random access" you might have better luck by creating a copy of that List that does provide this.

LinkedList<String> list = new LinkedList<String>();
// fill

Either like so

ArrayList<String> fastList = new ArrayList<String>(list);
Collections.binarySearch(fastList, "Hello World");

or maybe like so

String[] array = list.toArray(new String[list.size()]);
Arrays.binarySearch(array, "Hello World");

If your List is not ordered by default and you have to sort it prior to searching you might get the best result by doing it with arrays since

Collections.sort(list);

creates a temporary array that is sorted and used to re-create the list which you should be able to prevent if you do it with arrays directly.

String[] array = list.toArray(new String[list.size()]);
Arrays.sort(array);
Arrays.binarySearch(array, "Hello World");

Answer 2

The algorithm should be the same for both an ArrayList and a List, given they are both ordered.