Bash 脚本二进制搜索

Question

编写一个 bash 脚本来进行二分搜索。将文件中的学生姓名和成绩读入数组。提示用户输入学生姓名。在数组中查找名称并显示成绩。文件中的数据如下:

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

我已完成以下操作，但我不知道下一步该做什么

#!/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

二分搜索需要搜索的最大和最小边界。从零开始很好，但你的最后一个变量有点偏离。尝试:last=$(($#students[@]} - 1)) - 1 将使您的数组具有正确的大小(数组从零开始，然后减一。 )

然后尝试以下伪代码:

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

我不擅长 bash 脚本，所以我不会尝试修复(如果它甚至需要修复)你的大部分语法。如果您弄清楚语法，伪代码应该可以帮助您完成大部分工作。