Skip to content

Instantly share code, notes, and snippets.

@nicolonsky
Created November 2, 2020 13:20
Show Gist options
  • Save nicolonsky/5fe6fbe2039f479e4714e399933bec3c to your computer and use it in GitHub Desktop.
Save nicolonsky/5fe6fbe2039f479e4714e399933bec3c to your computer and use it in GitHub Desktop.
Binary Search Algorithm written in PowerShell
#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