Binary search

Hi,I have a Vector sorted on ID. How many objects should there be in the Vector for me to benefit on a binary search?Thanks!Erik

[156 byte] By [ek22cf@student.hik.sea] at [2007-10-1 17:42:25]

«« Java Web start Higher Version
»» JavaMail: How to hide the recipient address?

# 1

Do you mean at which point binary search becomes faster than linear search?There is an easy way to find out: try it!

sjasjaa at 2007-7-11 12:07:23 >

top of Java-index,Other Topics,Algorithms...

# 2

You may (or may not) be interested to know that in some practical tests I did with binary searching of Lists vs top-to-bottom searching, the binary search was very fast at all "n" values. However, the big stumbling block was the resort order for the index, even small numbers of objects can cause unacceptable delays in re-sorting the index...

If you really want to have binary searching, use a TreeMap (or similar R/B implementation)... much fasteroverall when considering for inserts and retrieves...

barryg2004a at 2007-7-11 12:07:23 >

# 3

If you think about it, by the time you are up to N = 3, in a binary search you will first look at the middle element and then if necessary either the first or the last. Thus it takes at most 2 comparisons and you have thus already shaved one comparison off of the possible mamimum that you will need to do.

The time it takes to add the top index to the bottom index and divide by 2 (the key step in finding the next element to look at in a binary search) is of course negligable i.e. on the same order as adding 1 to an index that is counting up and checking to see if you have gone too far. So it should be no surprise that binary search is essentially superior for all N.

It's only drawback being that the list does need to be sorted which may or may not be convenient as someone else mentioned.

marlin314a at 2007-7-11 12:07:23 >

# 4

Here is linear search:

if (arr[n] == value)

return n;

Here is binary search from java.util.Arrays:

int mid = (low + high) >> 1;

long midVal = a[mid];

if (midVal < key)

low = mid + 1;

else if (midVal > key)

high = mid - 1;

else

return mid; // key found

Which is faster? Depends. Array size, key distribution, percentage of misses, complexity of comparison (if it is more than "=="). At some point the simplicity of linear search is beaten by the smarts of the binary algorithm.

Seriousy: if you want to know, try it. I already did.

sjasjaa at 2007-7-11 12:07:23 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

Binary search

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified