BinarySearch

A Binary Search is a fast way of searching a sorted array.

For this to work:

• The array must be sorted in ascending order. QuickSort is good for this.
• The array to be searched is called MyArray.
• The Algorithm will return the element number if SearchString is found, otherwise it will return -1.
• The values Low and High represent the position range that is to be searched.

Algorithm

1. If High is smaller than Low produce -1 and quit the algorithm, as it has not found what it was looking for
2. Set Middle (the holder for the number of the partition element) to (Low+High)/2 - which would be the midle of the array.
3. If MyArray[Middle] is equal to SearchString (You've found it!) Return Middle and quit the algorithm.
   else, if SearchString is smaller than MyArray[Middle] then set High to Middle - 1, altering the range to be searched to the lower half of the current range.
   else, if SearchString is larger than MyArray[Middle] then set Low to Middle + 1, altering the range to be searched to the upper half of the current range.
4. Go back to 1.

Code

Function Int BinarySearch(Int Low, Int High, String SearchString)
{
//  low is the lower index, high is the upper index
//  of the region of array a that is to be sorted

    Local Int Middle;

    while (Low <= High) //only run while low is less than or equal to high.
        {
        Middle = (Low + High) / 2; //Set 'Middle' to be some midpoint
    
        if (MyArray[Middle] ~= SearchString) //if its found, return the array element
            Return Middle;

        if (MyArray[Middle] > SearchString) //if the SearchString is less, adjust the 'high' value accordingly.
            High = Middle - 1;
        else if (MyArray[Middle] < SearchString) //if the SearchString is more, adjust the 'low' value accordingly
            Low = Middle + 1;
        }
    Return -1; //if it fails, return -1.            
}

Related Topics

• Open Source
• QuickSort

Category Algorithm