Algorithms |
|
Searching |
|
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;
|
|