PowerShell Script to Perform Binary Search on Sorted Array

Use a PowerShell function like BinarySearch($arr, $target) that repeatedly checks the middle element and narrows the search range until the target is found or the range is empty.

Examples

Input[1, 3, 5, 7, 9], 5

Output2

Input[2, 4, 6, 8, 10, 12], 10

Output4

Input[10, 20, 30, 40, 50], 25

Output-1

How to Think About It

To do a binary search, think of the list as a book's pages. You open in the middle and check if the page number is what you want. If it's too high, you look in the left half; if too low, the right half. You keep cutting the search area in half until you find the target or run out of pages.

Algorithm

1

Set low index to 0 and high index to last element's index

2

While low is less than or equal to high:

3

Calculate middle index as the average of low and high

4

If middle element equals target, return middle index

5

If middle element is less than target, set low to middle + 1

6

Else set high to middle - 1

7

If not found, return -1

Code

powershell

function BinarySearch($arr, $target) {
    $low = 0
    $high = $arr.Length - 1
    while ($low -le $high) {
        $mid = [math]::Floor(($low + $high) / 2)
        if ($arr[$mid] -eq $target) { return $mid }
        elseif ($arr[$mid] -lt $target) { $low = $mid + 1 }
        else { $high = $mid - 1 }
    }
    return -1
}

# Example usage
$arr = @(1, 3, 5, 7, 9)
$target = 5
$result = BinarySearch $arr $target
Write-Output "Index of $target is $result"

Output

Index of 5 is 2

Dry Run

Let's trace searching for 5 in [1, 3, 5, 7, 9] through the code

1

Initialize

low=0, high=4 (array length - 1)

2

First middle check

mid = (0+4)/2 = 2, arr[2] = 5 matches target 5, return 2

low	high	mid	arr[mid]	action
0	4	2	5	Found target, return index 2

Why This Works

Step 1: Divide and conquer

The code splits the array into halves by calculating the middle index with mid = (low + high) / 2.

Step 2: Compare middle element

It compares the middle element with the target using -eq and decides which half to keep searching.

Step 3: Adjust search range

If the middle element is less than the target, it moves the low pointer up; otherwise, it moves the high pointer down.

Step 4: Return result

If the target is found, it returns the index; if not, it returns -1 to indicate absence.

Alternative Approaches

Recursive Binary Search

powershell

function RecursiveBinarySearch($arr, $target, $low, $high) {
    if ($low -gt $high) { return -1 }
    $mid = [math]::Floor(($low + $high) / 2)
    if ($arr[$mid] -eq $target) { return $mid }
    elseif ($arr[$mid] -lt $target) { return RecursiveBinarySearch $arr $target ($mid + 1) $high }
    else { return RecursiveBinarySearch $arr $target $low ($mid - 1) }
}

$arr = @(1,3,5,7,9)
$result = RecursiveBinarySearch $arr 5 0 ($arr.Length - 1)
Write-Output "Index of 5 is $result"

Uses function calling itself; easier to read but uses more memory due to call stack.

Using Array.IndexOf (Linear Search)

powershell

$arr = @(1,3,5,7,9)
$target = 5
$result = [Array]::IndexOf($arr, $target)
Write-Output "Index of $target is $result"

Simpler but slower for large arrays because it checks each element one by one.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search halves the search space each step, so it runs in logarithmic time relative to the array size.

Space Complexity

The iterative version uses constant extra space, only storing a few variables for indexes.

Which Approach is Fastest?

Iterative binary search is fastest and most memory efficient; recursive is easier to read but uses more stack space; linear search is slowest.

Approach	Time	Space	Best For
Iterative Binary Search	O(log n)	O(1)	Large sorted arrays, memory efficient
Recursive Binary Search	O(log n)	O(log n)	Readable code, small to medium arrays
Linear Search	O(n)	O(1)	Unsorted or small arrays