1

Quite simply, performance wise, how does using Arrays.binarySearch() compare to using an iterative loop (through all items in the array - a linear search) to find a value in an Array or ArrayList? Would the end user ever be able to see any delays using either?

Also are there any specific situations where one method is better than the other?

Andy
  • 3,600
  • 12
  • 53
  • 84
  • 4
    http://en.wikipedia.org/wiki/Binary_search_algorithm – NG. Jan 31 '14 at 21:20
  • 2
    NB binary search can and should be implemented iteratively/using a loop. I assume you mean linear search where every item of the list is checked until a match if found. –  Jan 31 '14 at 21:21
  • @delnan Yes, you assumed correctly. I'll edit my question – Andy Jan 31 '14 at 21:22
  • Brush up on some Big-O notation: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – Jonn Jan 31 '14 at 21:26
  • @Downvoters I don't mind downvotes but please explain why. This question already has multiple answers and seems useful – Andy Jan 31 '14 at 21:27
  • 3
    @Andy, I didn't down vote, but this is information that is easily looked up, and plentifully explained/discussed. I'm guessing the down votes are for lack of research effort. – turbo Jan 31 '14 at 21:28

5 Answers5

5

Binary search happens in O(log(n)) time. Linear search (that is, iterating the entire array) occurs in O(n) time. There's huge benefits in using binary search when and where you can.

In general, the situations in which you should use a binary search is when you're guaranteed that the data you have is sorted, and is above some minimum amount (since you won't notice much performance boost if you're searching 5 items with linear or binary search).

However, note that Arrays#binarySearch only works on arrays, and not ArrayList - those are fundamentally different objects. If you wanted a binary search on a List collection, then make use of Collections#binarySearch().

Makoto
  • 104,088
  • 27
  • 192
  • 230
  • Provided the array is sorted, and for a certain minimum size. – towr Jan 31 '14 at 21:21
  • That's the bar requirement for the binary search algorithm, anyway. But yes. – Makoto Jan 31 '14 at 21:22
  • Thanks for your answer, it is helpful. You mention that the data must be sorted, so what effect does using `Arrays.sort()` have on this comparence of performance. Also, the array would probably only ever be around 200 records so I don't suppose performance would be that noticable. – Andy Jan 31 '14 at 21:36
  • Well, log(200)/log(2) < 200, so you *would* notice some performance increase when searching (you'd have to ask a maximum of eight times as opposed to 200). Sorting the array would mean you take an O(n*log(n)) hit, since that's the performance of the Arrays#sort. By rule of Big-Oh notation, your overall runtime would be O(n*log(n)) because of the added, heavier cost of sorting the data. – Makoto Jan 31 '14 at 21:39
  • Thanks for that. Just to clarify then, if the array is unsorted then it's going to be quicker just to loop through each element of the array but if it is sorted then binary search is definately quicker. Sorry, I've never really met the Big-Oh notation before but I'm pretty sure I understand now. – Andy Jan 31 '14 at 21:50
1

Binary search requires that the array/list be sorted. This must be considered before performing such a search.

The benefit of a binary search is that the worst case run time is O(log(n)). On the other hand, the worst case for an iterative search is O(n), regardless of whether or not it has been sorted. Depending on the size of the array/list, and the data and its qualifications for order, the user may or may not notice a performance difference.

turbo
  • 1,887
  • 2
  • 21
  • 35
1

That will completely depend on the data in question. First, your array needs to be sorted. If your array is very small, you may not see a significant difference.

If your array is very large and sorted, you will see a significant speed increase when using a binary search.

Note: As your data set grows larger, binary search is increasingly faster. This is because of the nature of the growth of linear vs. logarithmic algorithms.

Jonn
  • 1,594
  • 1
  • 14
  • 25
1

If your array is sorted then you have to use binary search it will be very helpful and fast in execution with time complexity of O(logn) and in case array you have to call Arrays.binarySearch() and in case of any collection it might be the list or set you have to call Collections binarySearch method

Girish
  • 1,717
  • 1
  • 18
  • 30
0

Binary search works for Collections (ArrayList is implementation of it) too. Method is in java.util.Collections

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)`

Your element class should implement Comparable interface and implement public int compareTo(T o); method

Ashot Karakhanyan
  • 2,804
  • 3
  • 23
  • 28