# 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.
}```