Algorithms
Searching
 previous   up   next 

Recursive binary search in an array

A binary search locates an element in a sorted array by comparing the searched 'key' with the element in the middle of the array. Either the element is found or the process must be repeated for the first or second half of the array. The repetition of the search process is done with a recursive call. The binary search algorithm executes in O(log n) time.

const func integer: binarySearch (in array elemType: arr, in elemType: aKey, in integer: low, in integer: high) is func
  result
    var integer: index is 0;
  begin
    if low <= high then
      index := (low + high) div 2;
      if aKey < arr[index] then
        index := binarySearch(arr, aKey, low, pred(index)); # search left
      elsif aKey > arr[index] then
        index := binarySearch(arr, aKey, succ(index), high); # search right
      end if;
    end if;
  end func;

const func integer: binarySearch (in array elemType: arr, in elemType: aKey) is
  return binarySearch(arr, aKey, 1, length(arr));

Iterative binary search in an array

This algorithm implements binary search without recursive call. Instead the repetition of the search process is done in a loop. The binary search algorithm executes in O(log n) time.

const func integer: binarySearch2 (in array elemType: arr, in elemType: aKey) is func
  result
    var integer: index is 0;
  local
    var integer: low is 1;
    var integer: high is 0;
    var integer: middle is 0;
  begin
    high := length(arr);
    while index = 0 and low <= high do
      middle := (low + high) div 2;
      if aKey < arr[middle] then
        high := pred(middle);
      elsif aKey > arr[middle] then
        low := succ(middle);
      else
        index := middle;
      end if;
    end while;
  end func;

Linear search in an array

A linear or sequential search can be used to locate an element in an unsorted array. The elements are checked in sequence, until the desired one is found. The function below returns the index of the element found. If no element is found it returns 0. The linear search algorithm executes in O(n) time.

const func integer: linearSearch (in array elemType: arr, in elemType: aKey) is func
  result
    var integer: index is 0;
  begin
    index := length(arr);
    while index >= 1 and arr[index] <> aKey do
      decr(index);
    end while;
  end func;

Find the minimum element in an array

The function below returns the index of the minimum element in an array. For an empry array it returns 0. Since it is necessary to search the whole array it executes in O(n) time.

const func integer: findMinIndex (in array elemType: arr) is func
  result
    var integer: minIndex is 0;
  local
    var integer: index is 0;
    var elemType: minValue is elemType.value;
  begin
    if length(arr) <> 0 then
      minIndex := 1;
      minValue := arr[1];
      for index range 2 to length(arr) do
        if arr[index] < minValue then
          minIndex := index;
          minValue := arr[index];
        end if;
      end for;
    end if;
  end func;

Find the maximum element in an array

The function below returns the index of the maximum element in an array. For an empry array it returns 0. Since it is necessary to search the whole array it executes in O(n) time.

const func integer: findMaxIndex (in array elemType: arr) is func
  result
    var integer: maxIndex is 0;
  local
    var integer: index is 0;
    var elemType: maxValue is elemType.value;
  begin
    if length(arr) <> 0 then
      maxIndex := 1;
      maxValue := arr[1];
      for index range 2 to length(arr) do
        if arr[index] > maxValue then
          maxIndex := index;
          maxValue := arr[index];
        end if;
      end for;
    end if;
  end func;

 previous   up   next