| Home Page | Recent Changes | Preferences

# 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

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

Mapping Topics

Mapping Lessons

UnrealEd Interface

Questions&Answers

Scripting Topics

Scripting Lessons

Making Mods

Class Tree

Questions&Answers

Modeling Topics

Questions&Answers

Log In