Greetings In this thread place little micro-tutorials on how to code and use commonly used algorithms. For eg. A simple sorting algorithm, a bubble sort. What to use it for What not to use it for Why you should use it Problems with using it ect. I will edit my post to add the algorithms we have already used. Please note that double posts are allowed. Current index: Absolute function Binary search x2 Hash table Simple case boyer-moore string search Memory manager Bitreversing algorithm Recursive Floodfill Algoritithms awaiting a tutorial Complex Boyer-Moore string search algorithm Binary heap Quicksort From, Nice coder [Edited by - Nice Coder on January 9, 2005 4:58:43 AM]

Binary search

It searches a sorted array of values, for a particular value in o(log2 n) time (worst case).

This is a very fast search algorithm.
For eg, if you have an array that is 18,446,744,073,709,551,616 elements big, it will find any given element in at most 64 iterations.

Why is it that fast?

It is that fast, because at every comparison, it divides the search space in half. This means that after 2 iterations, the search space is 1/4 of the origional. this allows it to not search most of the array.

You should use it whenever you have an array, and you need to find a given element quickly. for eg, in a search engine, or pretty much anything.

psudocode:

Function binarysearch(array(), Element)max = upperbound(array)min = lowerbound(array)doGuess = makeinteger((max - min) / 2)if guess is negitive then return falureif array[guess] = element then	return guesselseif array[guess] > Element then	max = guess - 1elseif array[guess] < element then	min = guess + 1else	return falureend ifloop forever	

From,
Nice coder

[Edited by - Nice Coder on January 2, 2005 3:53:12 AM]

Well, I'd just point you to your CRLS or your Sedgewick algorithms books.

There is also the sometimes-helpful National Institute of Standards and Technology's Dictionary of Algorithms and Data Structures

Thats why this is here, so people can have a set of good algorithms, programmed in a language they can use, which contains more algorithms then then the stl.

From,
Nice coder

A fast string search.

Time complexity o(n / m) where n is the length of the string that your searching, and m is the length of the string your searching for.

Simple case, where each letter is used only once.

Psudocode:

function stringsearch(text, find)lof = lengthof(find)index = lofdoif the index'th carachter of text is equal to the last character of find then	check backwards, and see if the index - 2'th character of text is the same as the second last character of find.	Continue looping until you have checked the entire string. (Find), against the substring(string, index - lof,lof)	If you find an inequality then go back to the index += statement	otherwise, you have found your index = index + lofloop until index is larger then the length of the text

More complex case to follow

From,
Nice coder

Quote:Original post by Nice Coder

Function binarysearch(array(), Element)max = upperbound(array)min = lowerbound(array)doGuess = makeinteger((max - min) / 2)if guess is negitive then return falureif array[guess] = element then	return guesselseif array[guess] > Element then	max = guess - 1elseif array[guess] < element then	min = guess + 1else	return falureend ifloop forever	

A newbies guide to the binary search algorithm: All you thought you knew, and more...

You've made a very common major performance mistake (or two) here.
You've put the most unlikely if case first. The equal case should be the last case. Also since you have then already determined if it was < or > and acted appropriately then it must be equal so there is no test required. This cuts down the number of compares to about half what it was.

In fact, it's actually better if you leave the = part out of the loop entirely, since it's so rare, and only stop when min = max (at which point you will be at the item to compare for equality).
This all cuts it down to 1 compare per iteration, rather than the three you have above (try the biggest item). Performance also levels with exactly logn comparisons each time, rather than between 1 and 3logn (about 2.5logn on average)

Taking the = comparison out of the loop also has the unexpected advantage of making sure that you find the first occurance of an item which has duplicates in the array, which makes it easier to go through all duplicates (should that be of any usefullness in a given situation)
Or, if the item is known to be always present and you just what to find it's index, then the equals test can be removed entirely!

Now the C++ code...

Sure both are O(logn) so both are relatively fast, but a little extra thought effortlesssly gives you another 2x speedup + added niceities. Feel free to use the code above in your own programs. You may need to overload the < and == operators.
[smile]

No offence intended Nice Coder, just enlightening everybody furthur.

[Edited by - iMalc on January 2, 2005 2:35:17 PM]