# 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

- If High is smaller than Low produce -1 and quit the algorithm, as it has not found what it was looking for
- Set Middle (the holder for the number of the partition element) to (Low+High)/2 - which would be the midle of the array.
- 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. - 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. }