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).

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.

Why Use Binary Search?

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

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.

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.