Skip to main content

How to Perform a Binary Search on a Sorted List in Batch Script

When searching for a specific item in a large list (such as checking if a username is in a 1,000-entry "Denied" list)a standard linear search (checking every item from top to bottom) is very slow. A Binary Search is an efficient algorithm that finds the position of a target value within a sorted array. By repeatedly "Dividing and Conquering" the list, it can find an item in a list of 1,000 in only about 10 steps.

In this guide, we will demonstrate how to implement Binary Search using a "Low-Mid-High" pointer logic.

The Strategy: Divide and Conquer​

  1. Start with a low pointer at 1 and a high pointer at the end of the list.
  2. While low <= high:
    • Calculate the mid point: (low + high) / 2.
    • If Target == Array[mid], you found it!
    • If Target < Array[mid], search the lower half (move high to mid - 1).
    • If Target > Array[mid], search the upper half (move low to mid + 1).
warning

Binary search only works on sorted data. If your array is not already sorted in ascending order, the algorithm will produce incorrect results. Always sort your data first using the Bubble Sort technique or the native sort command before applying binary search.

Implementation Script​

@echo off
setlocal enabledelayedexpansion

:: 1. Setup a SORTED array
set "size=7"
set "ARR_1=10"
set "ARR_2=25"
set "ARR_3=30"
set "ARR_4=45"
set "ARR_5=50"
set "ARR_6=80"
set "ARR_7=99"

:: 2. Search Parameters
set /p "target=Enter number to find: "
set "low=1"
set "high=!size!"
set "foundAt=-1"

:: 3. Binary Search Loop
:search_loop
if !low! GTR !high! goto :done

:: Calculate Midpoint
set /a "mid=(low + high) / 2"

:: Use call to resolve the double-dynamic variable name
call set "val=%%ARR_!mid!%%"

echo Checking Index !mid! (Value !val!^)...

if !target! EQU !val! (
    set "foundAt=!mid!"
    goto :done
)

if !target! LSS !val! (
    :: Search Lower Half
    set /a "high=mid - 1"
) else (
    :: Search Upper Half
    set /a "low=mid + 1"
)
goto :search_loop

:done
echo.
if !foundAt! GEQ 0 (
    echo [MATCH] Found !target! at index !foundAt!.
) else (
    echo [FAIL] !target! not found in the list.
)

endlocal
pause

Example of output searching number 10:

Enter number to find: 10
Checking Index 4 (Value 45)...
Checking Index 2 (Value 25)...
Checking Index 1 (Value 10)...

[MATCH] Found 10 at index 1.

Example of output searching number 70:

Enter number to find: 70
Checking Index 4 (Value 45)...
Checking Index 6 (Value 80)...
Checking Index 5 (Value 50)...

[FAIL] 70 not found in the list.
  1. Performance: If you have a list of all your company's computer names (e.g., 5,000 names), a linear search is painfully slow in Batch. Binary search is nearly instantaneous.
  2. Validation: Quickly checking if a specific serial number or ID exists in a master inventory list before starting a deployment.
  3. Efficiency: Reducing the CPU and disk stress caused by long FOR loops and findstr calls by using memory-based logic.

Important Requirements​

note

Batch arithmetic is limited to signed 32-bit integers (approximately ±2.1 billion). Do not use this algorithm for values that exceed that range. For string-based binary searches, consider using PowerShell's built-in collection methods.

  1. A Sorted List is Mandatory: Binary search will not work on an unsorted list. You must first ensure your data is sorted alphabetically or numerically.
  2. Number Limits: As always, Batch is limited to 32-bit integers. Do not use this for values larger than ~2.1 billion.
  3. Case Sensitivity: When searching for strings, ensure your case matches or use internal if /i logic to handle variations.

Best Practices​

  1. Array Preparation: If your list is in a text file, read it into memory once at the start: for /f %%A in ('sort file.txt') do ....
  2. Exit Early: Once foundAt is set, exit the loop immediately to save cycles. The implementation above does this with goto :done.
  3. Use PowerShell for Strings: While Binary Search for numbers is easy in Batch, searching for strings is often more reliably handled by PowerShell's built-in .IndexOf or .Contains methods.
tip

To search in descending order, reverse the comparison logic: use LSS where the algorithm currently uses GTR and vice versa. The midpoint calculation remains the same.

Conclusion​

A binary search algorithm is a hallmark of efficient, high-performance scripting. By moving beyond simple "Top-to-Bottom" searches and utilizing the "Divide and Conquer" methodology, you can build tools that handle large datasets with the speed of a compiled program. This level of algorithmic sophistication is essential for professional system auditing and high-volume data validation.

Table of Contents