bash脚本二进制搜索 [英] Bash Script Binary Search

问题描述

写bash脚本做一个二进制搜索。从文件到一个数组中读取学生的姓名和成绩。提示输入学生姓名的用户。找到阵列中的名称，并显示品位。该文件中的数据是以下

 安：一
鲍勃：C
辛迪：乙
院长：F
艾米丽：一
弗兰克：C
姜：D
哈尔：乙
常春藤：一
贾斯汀：F
凯伦：D
 

我也做了以下但我卡在下一步该怎么做。

 ＃！/斌/庆典
 回声请输入学生姓名
 读学生
 回声$学生+ $级
 （（I = 0））
 而读学生[$ i];做
 （（我+ +）） 完成＆LT; students.dat
 首先= 0
 最后= $（学生[@]）
 （（MID = 0））
 名称=`回声$ {学生[$中旬]} |切-d：-f1`
 等级=`回声$ {学生[$中旬]} |切-d：-f2`
 回声$名称
 回声$级
 

解决方案

一个二进制搜索需求最大和搜索的最小边界。在零开始是伟大的，但你的最后一个变量是有点过。尝试：最后= $（（$＃学生[@]} - 1））的 - 1将使阵列在正确的大小（阵列零开始，到其规模少了一个。）

之后，请尝试以下伪code：

 而（去年为＆lt; =第一）
  第一个和最后的中间=中间点  //确保您的比较只是名字安
  //不是整个字符串安：A
  如果（学生[中] ==学生）
    出口环
  否则，如果（学生[中]＆LT;学生）
    第一中间= + 1
  否则，如果（学生[中]＆GT;学生）
    最后=中间 -  1
 

我不是在bash脚本编程很大，所以我不会尝试修复（如果它甚至需要修理）大部分的语法。伪code应该让你大多数的方式存在，如果你想出的语法。

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

解决方案

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.

这篇关于bash脚本二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！