Recursive PowerShell Binary Search Algorithm

I’ve been trying to solve a problem where I have a huge list of numbers within an array and I wanted to ensure that a number was present in this array. With arrays you have the option to use the Contains function but with huge arrays it may be much more efficient to check using a binary search.

During a quick search to see if I could leverage someone else’s implementation I found an interesting article. Only 10% of programmers can write a binary search routine! I figured it had been a very long time since I’ve done so and wanted to see if I could do it again. It wasn’t without trouble, but I managed to come up with a recursive routine.

Lo and behold:

function binarySearchContains($sortedArray, $number, $min, $max){

    $srchIndex = [Math]::Floor(($max - $min) / 2) + $min;
    #write-host "Binary search for number $number with index of $srchIndex (Max: $max, Min: $min) which is $($sortedArray[$srchIndex])"

    if($sortedArray[$srchIndex] -eq $number){
        #write-host "FOUND"
        return $true;
    }

    if($sortedArray[$srchIndex] -gt $number){
        if($max -eq $srchIndex){
            return $false;
        }
        $max = $srchIndex;
        #write-host "Going less. Max is now $srchIndex"
    }
    else{
        if($min -eq $srchIndex){
            return $false;
        }
        $min = $srchIndex;
        #write-host "Going More. Min is now $srchIndex"
    }

    return binarySearchContains $sortedArray $number $min $max
}

Usage:

The array (sortedArray) must be sorted as its name implies. $number is the number you wish to check for. $min represents the low end of the array index, being 0. $max represents the upper bound of the array (i.e. use $myData.Count).

Example

#Searches for number 40 in array ($mySortedArray) of numbers
binarySearchContains $mySortedArray 40 0 $mySortedArray.Count

Notes:

• Not largely tested, but it appears to work well from what I have done with it.
• I’m sure this could be tweaked to be more efficient. Feel free to post improvements and I will benchmark and update accordingly.
• The recursive call is left for last to keep it tail recursive. Whether or not this boosts efficiency in PowerShell, being a scripted language, I’m not sure!

Output:

Uncomment the portions that output debug text. Here is an example of the routine in action:

Array Data (22 Numbers)
12
18
20
24
30
36
40
42
48
54
56
60
66
70
72
78
80
84
88
90
96
100

Searching for 40

Binary search for number 40 with index of 11 (Max: 22, Min: 0) which is 60
Going less. Max is now 11
Binary search for number 40 with index of 5 (Max: 11, Min: 0) which is 36
Going More. Min is now 5
Binary search for number 40 with index of 8 (Max: 11, Min: 5) which is 48
Going less. Max is now 8
Binary search for number 40 with index of 6 (Max: 8, Min: 5) which is 40
FOUND
True