#
#
# \\\\ ////
# \\ - - //
# @ @
# ---oOOo-( )-oOOo---
#
# PowerShell Script: BinarySearch.ps1
# Author: Kevin Criss
#
# This is the classic binary search algorithm implemented in the Powershell Programming language.
# This algorithm is the heart and soul of any respectable search engine.
#
# Its also a very efficient way to search an array! Requires the array being searched to be pre-sorted in the sequence of your search key.
# This pre-sorting or pre-ordering the array in search-key sequence is a requirement of the binary search algorithm!
#
# How does it work and why do they call it the Binary Search, are we manipulating bits 1 and 0? No, were not doing anything with bits just pieces.
# A binary search always cuts the array into two pieces at the middle point. Then it checks the item being searched for against the contents at
# the middle point. If the contents at the middle point is greater than the item being search, the current middle point becomes the new high point
# and the array is cut in half again and re-tested. If the contents at the middle point is less than the item being searched, the current middle
# point becomes the new low point and the array is cut in half again and re-tested. This cutting in half and adjusting either the high point or the
# low point is repeated until the item is found or the low point and the high point converge. This is much faster then sequentially searching an
# entire array.
#
# Additional Reference:
# http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
# Thank you Mr. Bloch for sharing the patch to this classic algorithm via your Google Research Blog. I have incorporated the new formula you
# are reporting for calculating the $script:MiddlePoint into this routines.
#
#
################################################
# Function: PowerShell Binary Search Algorithm #
################################################
#
function BinarySearch
{
Param ($YourOrderedArray, $ItemSearched)
[int] $LowIndex = 0
[int] $HigIndex = $YourOrderedArray.length - 1
while ($LowIndex -le $HigIndex)
{
# [int]$script:MiddlePoint = ($LowIndex + $HigIndex) / 2
[int]$script:MiddlePoint = $LowIndex + (($HigIndex - $LowIndex) / 2)
$InspectedValue = $YourOrderedArray[$script:MiddlePoint].YourObjectSearched
If ($InspectedValue -lt $ItemSearched)
{
$LowIndex = $script:MiddlePoint + 1
}
Elseif ($InspectedValue -gt $ItemSearched)
{
$HigIndex = $script:MiddlePoint - 1
}
Else
{
$script:ItemFound = $True
return
}
}
$script:ItemFound = $False
$script:MiddlePoint = -($LowIndex + 1)
return
}
################################################
# Main Routine #
################################################
# Usage:
BinarySearch $MySearchKey $MyArray_Presorted_in_searchkey_Sequence
#
# Returns ($script:ItemFound = $True and the $script:MiddlePoint indexing the location of the item)
# or
# Returns ($script:ItemFound = $False
# and $script:MiddlePoint equal to the negative value of $YourOrderedArray.length +1) |