如何在Bash中进行内存中的二进制search?

写一个bash脚本来做二进制search。 从一个文件读取学生姓名和成绩到一个数组中。 提示用户input学生姓名。 在数组中find名称并显示分数。 该文件中的数据如下:

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 

Solutions Collecting From Web of "如何在Bash中进行内存中的二进制search?"

这里的每一个人都希望你学习这些东西,而不是为你做任务,所以我故意做一个小傻瓜。

请记住,这里提出的任何解决方案都是一个程序员如何做,不一定是一个真正的方法。

您需要首先将您的成绩纳入您的计划 – 从此开始。 文件中的每一行都是一个以“:”分隔的学生名称。 你想把它们读成两个平行的数组(正如Jonathan指出的那样)。

如果你谷歌'bash拆分字符串',你会发现很多有用的建议,如何做到这一点。 我这样做了两个数组,一个拿着学生名字,另一个拿着成绩。

 ((i=0)) while IFS=":" read -a fields ; do students[$i]=${fields[0]} grades[$i]=${fields[1]} ((i++)) done < students.dat echo ${students[@]} echo ${grades[@]} 

凉! 现在您需要稍微处理二分查找算法。 请记住,您可以使用${#ArrayName[@]}获取数组的长度

由于列表显然已经排序了,所以你不必自己做,所以你可以在数组中点比较你想要的名字和学生的名字。 如果你正在寻找的学生名字比中间点的学生名字要大,那么你知道你想要的那个名字是在数组的后半部分,反之亦然。 最终,学生在中点的名字就是你正在寻找的名字。

如果不需要在bash那么你可以使用awkbash仅在版本4中启动了关联数组,因此可移植性可能是您需要考虑的事情。

如果awk不适用于您,则忽略该解决方案:

 $ awk -F: '{ student[$1] = $2 } END { printf "Enter Student Name: "; getline name < "-"; print "Grade for student "name" is "student[name] }' inputFile 

测试:

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

 $ awk -F: '{ student[$1] = $2 } END { printf "Enter Student Name: "; getline name < "-"; print "Grade for student "name" is "student[name] }' inputFile Enter Student Name: Justin Grade for student Justin is F 

这里是一个正在工作的二进制搜索bash脚本,为仍在搜索的学生。

  binary_search(){ TARGET=$1 TO_SEARCH=(${@:2}) LENGTH=${#TO_SEARCH[@]} START=0 END=$((LENGTH - 1)) while [[ $START -le $END ]]; do MIDDLE=$((START + ((END - START)/2))) ITEM_AT_MIDDLE=${TO_SEARCH[MIDDLE]} if [[ $ITEM_AT_MIDDLE -gt $TARGET ]]; then END=$((END-MIDDLE-1)) elif [[ $ITEM_AT_MIDDLE -lt $TARGET ]]; then START=$((MIDDLE+1)) else echo $MIDDLE return 0 fi done echo "-1" return 0 }​