Created
November 2, 2020 13:20
-
-
Save nicolonsky/5fe6fbe2039f479e4714e399933bec3c to your computer and use it in GitHub Desktop.
Binary Search Algorithm written in PowerShell
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Binary search algorithm with O(logn) complexity written in PowerShell | |
function Invoke-BinarySearch { | |
[CmdletBinding()] | |
[OutputType([int])] | |
param ( | |
# Array which contains value to search, needs to be sorted | |
[Parameter(Mandatory)] | |
[int[]] | |
$Numbers, | |
# Value to search for | |
[Parameter(Mandatory)] | |
[int] | |
$Value | |
) | |
begin { | |
# ensure values are sorted | |
} | |
process { | |
$start = -1 | |
$end = $Numbers.Length | |
$count = 0 | |
while ($end -gt $start + 1) { | |
Write-Verbose "Binary search iteration $count" | |
[int]$i = ($start + $end) / 2 | |
if ($Value -lt $Numbers[$i]) { | |
$end = $i | |
} | |
elseif ($Value -gt $Numbers[$i]) { | |
$start = $i | |
} | |
elseif ($Value -eq $Numbers[$i]) { | |
return $i | |
} | |
$count++ | |
} | |
Write-Warning "Value $Value not found! (Max $(2 -shl $count) searches for array with $($Numbers.Length) elements)" | |
return -1 | |
} | |
end { | |
} | |
} | |
$numbers = 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 18, 21, 23, 27, 29, 31, 37, 39, 41, 43, 45, 47, 51, 56, 17, 18, 99 | |
$searchFor = 100 | |
Invoke-BinarySearch -Numbers $numbers -Value $searchFor -Verbose |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment