Bash 脚本二进制搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17666007/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Bash Script Binary Search
提问by user2585390
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:
编写一个 bash 脚本来进行二分查找。将文件中的学生姓名和成绩读入数组。提示用户输入学生姓名。在数组中查找名称并显示等级。文件中的数据如下：
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
回答by David Mann
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.)
二分搜索需要搜索的最大和最小边界。从零开始很好，但你的最后一个变量有点偏离。尝试：last=$(($#students[@]} - 1))- 1 会将您的数组置于正确的大小（数组从零开始并减少其大小的一个。）
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 脚本，所以我不会尝试修复（如果它甚至需要修复）你的大部分语法。如果您弄清楚语法，伪代码应该可以帮助您完成大部分工作。
回答by OlivierBlanvillain
This solution assumes that you are looking for the first successful execution of a command, rather than an element in an array.
此解决方案假定您正在寻找命令的第一次成功执行，而不是数组中的元素。
lo=1
hi=100
while [ $(expr $hi - $lo) -ne 1 ]; do
mid=$(expr $lo + '(' $hi - $lo ')' / 2)
# Your command here
test 44 -gt $mid
if [ $? -eq 0 ]; then lo=$mid; else hi=$mid; fi
done
echo "$lo"
This always print the firstvalue for which the execution of your command succeeds, unlike @lovasoa solution that is off by one in about half of the configurations. You can validate that by using seq 1 100 | while read o; do SCRIPT; donewhere SCRIPTis the above algorithm with test $o -gt $midas the tested command.
这始终打印命令执行成功的第一个值，这与 @lovasoa 解决方案不同，后者在大约一半的配置中相差一个。您可以通过使用上面的算法seq 1 100 | while read o; do SCRIPT; donewhere SCRIPTistest $o -gt $mid作为测试命令来验证这一点。
回答by Kehinde Omotoso
Try this and let me get your feedback.
试试这个，让我得到你的反馈。
#!/bin/bash
##CREATE AN ARRAY VARIABLE TO STORE DATA FOUND IN STUDENT.TXT AT STARTUP
#NAMESARRAY STORE ALL NAMES
declare -a namesarray
#GRADESARRAY STORE ALL GRADES
declare -a gradesarray
#GLOBALMATCHINDEX STORES THE ARRAY INDEX WHERE NAME IS FOUND.... NAMES ARRAY START FROM 0
globalmatchindex=-1
#FUNCTION "CONTAINS" SEARCH THROUGH NAMESARRAY VAIRIABLE TO FIND INPUT FROM USER
function contains(){
#CREATE 2 VARIABLES "e" AND "match"
local e match=""
shift
#VARIABLE matchindex IS A LOCAL VARIABLE IN THE "CONTAINS" FUNCTION THAT TEMPORARILY STORES THE VALUE OF THE INDEX WHERE INPUTED NAME IS FOUND IN namesarray VARIABLE
local matchindex=0
#LOOP THROUGH namesarray GLOBAL VARIABLE WHICH WAS PASSED AS A PARAMETER TO THE "CONTAINS" FUNCTION
for e;
do
#CHECK IF A MATCHING STRING IS FOUND IN THE namesarray GLOBAL VARIABLE WHICH WAS PASSED AS A PARAMETER
if [ "$e" == "$match" ]; then
#SET THE VALUE OF globalmatchindex GLOBAL VARIABLE TO THE CURRENT LOOP INDEX ALIAS matchindex
globalmatchindex=$matchindex
#EXIT LOOP AND CONTINUE PROCESS
break
fi
#INCREMENT LOCAL matchindex VARIABLE FOR THE NEXT ROUND OF LOOP
matchindex=$((matchindex+1))
done
}
#FUNCTION "CONTAINS" END HERE
#linenumber GLOBAL VARIABLE STORES THE CURRENT LINE NUMBER IN students.txt FILE
linenumber=0
#A LOOP THAT READ ENTIRE student.txt FILE
while read line; do
#SINCE THE NAMES AND GRADES ARE SEPARATED BY ":" CHARACTER, WE USE A STRING SPLIT METHOD TO SEPARATE NAME FROM GRADE
IFS=':'
#READ EACH LINE AS ARRAY TO "LINEARRAY" VARIABLE. "LINEARRAY" VARIABLE CONTAINS CONTENT LIKE SO "LINEARRAY[0]='JAMES'", "LINEARRAY[1]='A'"
read -ra LINEARRAY <<< "$line"
#STORE THE FIRST STRING IN namesarray GLOBAL VARIABLE
namesarray[$linenumber]=${LINEARRAY[0]}
#STORE THE SECOND STRING IN gradesarray GLOBAL VARIABLE
gradesarray[$linenumber]=${LINEARRAY[1]}
linenumber=$((linenumber+1))
done < students.txt
while true; do
echo "Enter Student name:"
read studentname
contains "$studentname" "${namesarray[@]}"
if [ $globalmatchindex -gt -1 ]; then
echo "Hello ${namesarray[$globalmatchindex]} your grade is ${gradesarray[$globalmatchindex]}"
else
echo "Student not found."
fi
globalmatchindex=-1
done
The content of the student.txt file is below.
student.txt 文件的内容如下。
Ann:A
Bob:C
Cindy:B
Dean:F
Emily:A
Frank:C
Ginger:D
Hal:B
Ivy:A
Justin:F
Karen:D
回答by lovasoa
I think it's best to use a generic binary search function then to code your own for your particular case.
我认为最好使用通用的二进制搜索函数，然后为您的特定情况编写自己的代码。
Binary search function in bash
bash中的二进制搜索功能
# Returns the largest i for which `command i` succeeds (exits with a null exit code)
function dichotomic_search {
min=
max=
command=
while [ $min -lt $max ]; do
# Compute the mean between min and max, rounded up to the superior unit
current=`expr '(' "$min" + "$max" + 1 ')' / 2`
if $command $current
then min=$current
else max=`expr $current - 1`
fi
done
echo $min
}
It calls the function given as its last argument repetitively using binary search to find the last value for which it returns true. More explanations on Github
它使用二进制搜索重复调用作为其最后一个参数给出的函数，以找到返回 true 的最后一个值。Github上的更多解释
Binary search through a bash array
通过 bash 数组进行二分搜索
In your case, you would use it like that:
在你的情况下，你会这样使用它：
#!/usr/bin/env bash
source dichotomic.sh
arr=(Ann:C Bob:A Cindy:B Dean:E Emily:A Karen:A Zob:A)
function is_smaller {
element=$(echo ${arr[]} | cut -f1 -d :)
if [[ "$element" > "" ]]
then false
else true
fi
}
read target
highest_index=`expr ${#arr[@]} - 1`
index=$(dichotomic_search 0 $highest_index "is_smaller $target")
echo "${arr[$index]}"
