Bash Script Binary Search

Question

Write a bash script to do a binary search. Read student names and grades from a file into an array. Prompt the user for a student name. Find the name in the array and display the grade. The data in the file is below:

Ann:A
Bob:C
Cindy:B
Dean:F
Emily:A
Frank:C
Ginger:D
Hal:B
Ivy:A
Justin:F
Karen:D

I have done the following but I am stuck on what to do next

#!/bin/bash
 echo "please enter students Name: "
 read student
 echo "$student + $Grade"
 ((i=0))
 while read students[$i] ; do
 ((i++))

 done < students.dat
 first=0
 last=$(students[@])


 ((mid=0))
 Name=`echo ${students[$mid]} | cut -d: -f1`
 Grade=`echo ${students[$mid]} | cut -d: -f2`
 echo $Name
 echo $Grade

Answer 1

A binary search needs the max and min boundaries of the search. Starting at zero is great, but your last variable is a little off. Try: last=$(($#students[@]} - 1)) the - 1 will put your array at the correct size (arrays start at zero and go to one less of their size.)

After that try the following pseudo code:

while (last is <= first) 
  middle = midway point between first and last

  // make sure that your comparing just the names "Ann",
  // not your whole string "Ann:A"
  if (students[middle] == student)
    exit loop
  else if (students[middle] < student)
    first = middle + 1
  else if (students[middle] > student)
    last = middle - 1

I'm not great at bash scripting, so I won't try and fix (if it even needs fixing) most of your syntax. The pseudo code should get you most of the way there if you figure out the syntax.

Answer 2

This solution assumes that you are looking for the first successful execution of a command, rather than an element in an array.

lo=1
hi=100
while [ $(expr $hi - $lo) -ne 1 ]; do
  mid=$(expr $lo + '(' $hi - $lo ')' / 2)

  # Your command here
  test 44 -gt $mid

  if [ $? -eq 0 ]; then lo=$mid; else hi=$mid; fi
done
echo "$lo"

This always print the first value for which the execution of your command succeeds, unlike @lovasoa solution that is off by one in about half of the configurations. You can validate that by using seq 1 100 | while read o; do SCRIPT; done where SCRIPT is the above algorithm with test $o -gt $mid as the tested command.

Answer 3

I think it's best to use a generic binary search function then to code your own for your particular case.

Binary search function in bash

# Returns the largest i for which `command i` succeeds (exits with a null exit code)
function dichotomic_search {

  min=$1
  max=$2
  command=$3

  while [ $min -lt $max ]; do
    # Compute the mean between min and max, rounded up to the superior unit
    current=`expr '(' "$min" + "$max" + 1 ')' / 2`
    if $command $current
      then min=$current
      else max=`expr $current - 1`
    fi
  done

  echo $min
}

It calls the function given as its last argument repetitively using binary search to find the last value for which it returns true. More explanations on Github

Binary search through a bash array

In your case, you would use it like that:

#!/usr/bin/env bash

source dichotomic.sh
arr=(Ann:C Bob:A Cindy:B Dean:E Emily:A Karen:A Zob:A)

function is_smaller {
  element=$(echo ${arr[$2]} | cut -f1 -d :)
  if [[ "$element" > "$1" ]]
    then false
    else true
  fi
}

read target
highest_index=`expr ${#arr[@]} - 1`
index=$(dichotomic_search 0 $highest_index "is_smaller $target")
echo "${arr[$index]}"

Answer 4

Try this and let me get your feedback.

#!/bin/bash
##CREATE AN ARRAY VARIABLE TO STORE DATA FOUND IN STUDENT.TXT AT STARTUP
#NAMESARRAY STORE ALL NAMES
declare -a namesarray
#GRADESARRAY STORE ALL GRADES
declare -a gradesarray

#GLOBALMATCHINDEX STORES THE ARRAY INDEX WHERE NAME IS FOUND.... NAMES ARRAY START FROM 0
globalmatchindex=-1

#FUNCTION "CONTAINS" SEARCH THROUGH NAMESARRAY VAIRIABLE TO FIND INPUT FROM USER
function contains(){
    #CREATE 2 VARIABLES "e" AND "match"
    local e match="$1"
    shift
    #VARIABLE matchindex IS A LOCAL VARIABLE IN THE "CONTAINS" FUNCTION THAT TEMPORARILY STORES THE VALUE OF THE INDEX WHERE INPUTED NAME IS FOUND IN namesarray VARIABLE
    local matchindex=0
    #LOOP THROUGH namesarray GLOBAL VARIABLE WHICH WAS PASSED AS A PARAMETER TO THE "CONTAINS" FUNCTION
    for e;
    do  
        #CHECK IF A MATCHING STRING IS FOUND IN THE namesarray GLOBAL VARIABLE WHICH WAS PASSED AS A PARAMETER
        if [ "$e" == "$match" ]; then
            #SET THE VALUE OF globalmatchindex GLOBAL VARIABLE TO THE CURRENT LOOP INDEX ALIAS matchindex
            globalmatchindex=$matchindex
            #EXIT LOOP AND CONTINUE PROCESS
            break
        fi
    #INCREMENT LOCAL matchindex VARIABLE FOR THE NEXT ROUND OF LOOP
    matchindex=$((matchindex+1))
    done
}
#FUNCTION "CONTAINS" END HERE

#linenumber GLOBAL VARIABLE STORES THE CURRENT LINE NUMBER IN students.txt FILE
linenumber=0
#A LOOP THAT READ ENTIRE student.txt FILE
while read line; do
    #SINCE THE NAMES AND GRADES ARE SEPARATED BY ":" CHARACTER, WE USE A STRING SPLIT METHOD TO SEPARATE NAME FROM GRADE
    IFS=':'
    #READ EACH LINE AS ARRAY TO "LINEARRAY" VARIABLE. "LINEARRAY" VARIABLE CONTAINS CONTENT LIKE SO "LINEARRAY[0]='JAMES'", "LINEARRAY[1]='A'"
    read -ra LINEARRAY <<< "$line"
    #STORE THE FIRST STRING IN namesarray GLOBAL VARIABLE
    namesarray[$linenumber]=${LINEARRAY[0]}
    #STORE THE SECOND STRING IN gradesarray GLOBAL VARIABLE
    gradesarray[$linenumber]=${LINEARRAY[1]}
    linenumber=$((linenumber+1))
done < students.txt

while true; do
    echo "Enter Student name:"
    read studentname
    contains "$studentname" "${namesarray[@]}"
    if [ $globalmatchindex -gt -1 ]; then
        echo "Hello ${namesarray[$globalmatchindex]} your grade is ${gradesarray[$globalmatchindex]}"
    else
        echo "Student not found."
    fi
    globalmatchindex=-1

done

The content of the student.txt file is below.

Ann:A
Bob:C
Cindy:B
Dean:F
Emily:A
Frank:C
Ginger:D
Hal:B
Ivy:A
Justin:F
Karen:D