bash script to do binary search and store values in an array

Question

I need an idea on how to complete this research project:

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. If the student does not exist, print a message stating that.

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

Answer 1

Just a note about the binary search approach. Using greater-than / less-than to check whether the user's provided name is below or above the current name in the array works because the names are conveniently in alphabetical order (meaning that the person who gave you this assignment wanted you take advantage of this convenience).

The Code:

# Store the names and grades into arrays
names=( $( cut -d: -f1 filename ) )
grades=( $( cut -d: -f2 filename ) )

# Prompt user for a name
echo "Type the student's name (use proper capitalization!), followed by [ENTER]:"

# Read the user's response
read name

length=${#names[@]}
start=0
end=$((length - 1))
match=0
while [[ $start -le $end ]]; do
     middle_i=$((start + ((end - start)/2)))
     middle_item=${names[$middle_i]}
     if [[  $middle_item -gt $name ]]; then
         end=$((end - middle_i-1))
     elif [[ $middle_item -lt $name ]]; then
         start=$((middle_i+1))
     else
         # A match was found
         match=1
         echo "${name}'s grade is a(n): ${grades[$middle_i]}."
         break
     fi
done

# Check if a match was found
if [[ $match = 0 ]]; then
    echo "Couldn't find that student..."
fi

If you don't find the binary search to be a very readable approach, as I do, then I'd recommend using a for-loop:

# Find the user's provided name, print the 
for i in "${!names[@]}"; do
    # Check if the current name in the array is the same as the provided name
    if [[ "${names[$i]}" = "${name}" ]]; then
        # A match was found
        match=1
        echo "${name}'s grade is a(n): ${grades[$i]}."
        break
    fi
done

For the cut command, if you are not familiar...

-d: specifies the delimiter used in your given text file.

-f: specifies which field to keep (and thus store into the array).

Explaining the Code:

1. You can think of the text file you have as a CSV file, except for : is used instead of , as a delimiter. For this reason, I use -d:. There are two columns, (i.e., two fields) per line in your text file.
2. A field is essentially equivalent to a column in a CSV file. The fields are separated by the delimiter, :. The first field contains the student's name, so I used -f1 to capture the students' names. The second field contains the student's grade, so I used -f2 to capture the students' grades.

Done! Happy coding