Bash Script for Binary Search with Example and Explanation

Use a Bash script that repeatedly divides the sorted array by checking the middle element with mid=$(( (low + high) / 2 )) and adjusts low or high until the target is found or the search space is empty.

Examples

Inputarray=(1 3 5 7 9) target=7

OutputElement 7 found at index 3

Inputarray=(2 4 6 8 10 12) target=5

OutputElement 5 not found in the array

Inputarray=(10) target=10

OutputElement 10 found at index 0

How to Think About It

To perform binary search in Bash, think of the array as a sorted list where you check the middle element first. If the middle element is the target, you stop. If the target is smaller, you search the left half; if larger, the right half. Repeat this until you find the target or the search space is empty.

Algorithm

1

Set low to 0 and high to the last index of the array

2

While low is less than or equal to high:

3

Calculate mid as the average of low and high

4

If the element at mid equals the target, return mid

5

If the element at mid is less than target, set low to mid + 1

6

Else set high to mid - 1

7

If loop ends without finding target, return not found

Code

bash

binary_search() {
  local arr=(${!1})
  local target=$2
  local low=0
  local high=$((${#arr[@]} - 1))

  while (( low <= high )); do
    local mid=$(((low + high) / 2))
    if (( arr[mid] == target )); then
      echo "Element $target found at index $mid"
      return
    elif (( arr[mid] < target )); then
      low=$((mid + 1))
    else
      high=$((mid - 1))
    fi
  done
  echo "Element $target not found in the array"
}

# Example usage
array=(1 3 5 7 9)
target=7
binary_search array[@] $target

Output

Element 7 found at index 3

Dry Run

Let's trace searching for 7 in array (1 3 5 7 9) through the code

1

Initialize variables

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

2

First iteration

mid=(0+4)/2=2, arr[mid]=5, 5 < 7, so low=mid+1=3

3

Second iteration

mid=(3+4)/2=3, arr[mid]=7, equals target, found at index 3

Iteration	low	high	mid	arr[mid]	Action
1	0	4	2	5	5 < 7, set low=3
2	3	4	3	7	Found target at index 3

Why This Works

Step 1: Divide and conquer

The script splits the array by calculating the middle index with mid=$(((low + high) / 2)) to check the middle element.

Step 2: Adjust search range

If the middle element is less than the target, it moves the low pointer up to search the right half; otherwise, it moves the high pointer down to search the left half.

Step 3: Stop condition

The loop stops when the target is found or when low exceeds high, meaning the target is not in the array.

Alternative Approaches

Recursive binary search

bash

binary_search_recursive() {
  local arr=(${!1})
  local target=$2
  local low=$3
  local high=$4
  if (( low > high )); then
    echo "Element $target not found in the array"
    return
  fi
  local mid=$(((low + high) / 2))
  if (( arr[mid] == target )); then
    echo "Element $target found at index $mid"
  elif (( arr[mid] < target )); then
    binary_search_recursive arr[@] $target $((mid + 1)) $high
  else
    binary_search_recursive arr[@] $target $low $((mid - 1))
  fi
}

# Example usage
array=(1 3 5 7 9)
target=7
binary_search_recursive array[@] $target 0 $((${#array[@]} - 1))

Uses function calls instead of loops; easier to read but less efficient in Bash due to call overhead.

Linear search (alternative)

bash

linear_search() {
  local arr=(${!1})
  local target=$2
  for i in "${!arr[@]}"; do
    if (( arr[i] == target )); then
      echo "Element $target found at index $i"
      return
    fi
  done
  echo "Element $target not found in the array"
}

# Example usage
array=(1 3 5 7 9)
target=7
linear_search array[@] $target

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

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

Time Complexity

Binary search divides the search space in half each iteration, 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 in Bash; recursive adds call overhead, and linear search is slower for large arrays.

Approach	Time	Space	Best For
Iterative Binary Search	O(log n)	O(1)	Large sorted arrays
Recursive Binary Search	O(log n)	O(log n) due to call stack	Readability, small arrays
Linear Search	O(n)	O(1)	Unsorted or small arrays