Bash Script Binary Search
bash, binary-search
Solution
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.
Problem
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 ```