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 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.
Hop
