| 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


Category Algorithm

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

FAQs

Help Desk

Mapping Topics

Mapping Lessons

UnrealEd Interface

UnrealScript Topics

UnrealScript Lessons

Making Mods

Class Tree

Modeling Topics

Chongqing Page

Log In