Binary search, or "Busca Binária" in Portuguese, is a fundamental algorithm in computer science used to find the position of a target value within a sorted array. It is highly efficient with a time complexity of O(log n), making it an essential technique for optimizing search operations. While binary search is typically discussed in the context of programming languages like Python, Java, or C++, it can also be implemented in a Linux environment using shell scripts.

In this article, we will explore how to create a binary search algorithm using Bash, the default shell in most Linux distributions. This will be particularly useful for systems engineers and administrators who need to perform efficient searches on sorted data directly from the command line.

Examples:

1. Creating a Sorted Array:

First, let's create a sorted array of numbers. This array will be used as the input for our binary search algorithm.

   #!/bin/bash



   # Sorted array of numbers

   sorted_array=(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39)

2. Binary Search Function:

Next, we will define a function that performs binary search on the sorted array. The function will take the target value as an argument and return the index of the target if found, or -1 if not found.

   #!/bin/bash



   # Binary search function

   binary_search() {

       local array=("$@")

       local target=${array[-1]}

       unset array[-1]



       local low=0

       local high=$((${#array[@]} - 1))



       while [ $low -le $high ]; do

           local mid=$(( (low + high) / 2 ))

           if [ ${array[mid]} -eq $target ]; then

               echo $mid

               return 0

           elif [ ${array[mid]} -lt $target ]; then

               low=$((mid + 1))

           else

               high=$((mid - 1))

           fi

       done



       echo -1

       return 1

   }



   # Example usage

   sorted_array=(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39)

   target=19

   index=$(binary_search "${sorted_array[@]}" $target)



   if [ $index -ne -1 ]; then

       echo "Target found at index: $index"

   else

       echo "Target not found"

   fi

3. Running the Script:

Save the script to a file, for example binary_search.sh, and make it executable:

   chmod +x binary_search.sh

Run the script to see the binary search in action:

   ./binary_search.sh

The output should be:

   Target found at index: 9