Web Development

General discussion


C++ Linear Search / Binary Search???

By Mr_joey ·
I have been told that the Binary Search Method in C++ Programming is much better than the linear search method. I was wondering if someone could please explain to me why that is. I looking for a little bit of depth, because I understand it somewhat,but just expound on it for me.

Please E-mail me if you exceed the Max Length (1930 Characters).



This conversation is currently closed to new comments.

Thread display: Collapse - | Expand +

All Comments

Collapse -

C++ Linear Search / Binary Search???

by Geert Pante In reply to C++ Linear Search / Binar ...

This is not specific for C++ Programming, off course, in C, C# and in Java, Binary search is faster too. And your list needs to be sorted to do a binary search in any language, too.

Let's assume you have an list of 1000 elements composed of a key and a value, and you have to search the value for a particular key in it a 100 times.

In linear search, you'd start each time at the beginning of the list, and at avg after 500 elements you'd find it. So that would take you 50,000 elements at avg to evaluate.

In binary search, you start with sorting the list by key. Then, to search a key, you start at the item at position 512. If it is equal, you find it after 1 step, if your key is smaller, you go to 512-256 = 256, if it is bigger, you go to 512+256 =768. Next if your key is at 768 or 256, you found it after 2 steps, otherwise if it is bigger, add 128 to the position, if it is smaller, substract 128. Continue with numbers 64, 32, 16, 4, 2 and 1. This way, you will certainly find your key after max 10 steps (avg 9 or something). To sort the whole set, there are algorithms that follows the same pattern: avg 9 comparisons times a 1000 elements equals 9,000 comparisons to sort.
So to search a 100 items you need 9,000 comparisons to sort, and 900 to find your elements, which totals 9,900, 5 times faster than linear search (50,000).

It gets better for bigger numbers:
search 500 in 1000, lineair: 250,000, binary: 9000+9*500=13,500, ~20 times faster.
search 100,000 in 1,000,000, lineair: 50 billion,
for binary, it takes avg 19 comparisons for a binary search or to sort 1 element, so we have 20,900,000 comparisons in total, 2000 times faster than lineair.

If you use C++, you don't even have to implement the algorithm. In the STL std::map<key, value> does it all out-of-the box: items are sorted as they are inserted, and binary search is what the operator[] does behind the scenes.


Collapse -

C++ Linear Search / Binary Search???

by Mr_joey In reply to C++ Linear Search / Binar ...

Thanks for laying this out for me. Really helped me a lot!

Collapse -

C++ Linear Search / Binary Search???

by Mr_joey In reply to C++ Linear Search / Binar ...

This question was closed by the author

Related Discussions

Related Forums