Bash 스크립트 바이너리 검색

바이너리 검색을위한 bash 스크립트를 작성하십시오. 파일에서 학생 이름과 성적을 배열로 읽어보십시오. 사용자에게 학생 이름을 묻습니다. 배열에서 이름을 찾아 등급을 표시하십시오. 파일의 데이터는 다음과 같습니다 : 나는 다음과 같은 짓을하지만 난 이진 검색은 최대 및 검색의 분 경계를 필요로Bash 스크립트 바이너리 검색

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

출처

2013-07-16 user2585390

이진 검색 설정 방법에 대한 이해가 있습니까? 예를 들어, 종이에 단계별로 적용 할 수 있습니까? – Kon

이 문제의 원인은 무엇입니까? https://emp.byui.edu/olavesonm/cit352/a10.htm에 버전이 있습니다. –

다음에 무엇을해야하는지에 부착하고

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

. 0부터 시작하는 것이 좋지만 마지막 변수는 약간 떨어져 있습니다. (1) 올바른 크기로 배열을 넣어 것입니다 (배열은 0에서 시작과 크기의 작은 하나로 이동합니다.)

을 그 다음 의사 코드 시도 후 - (가) last=$(($#students[@]} - 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 스크립팅에서는별로 좋지 않으므로, 대부분의 구문을 고치려고하지는 않습니다. 의사 코드는 구문을 파악할 때 거기에서 가장 많은 것을 얻을 수 있습니다.

출처

2013-07-17 11:00:35

일반 이진 검색 기능을 사용하여 특정 경우에 맞게 코드를 작성하는 것이 가장 좋습니다.

Binary search function in bash

# Returns the largest i for which `command i` succeeds (exits with a null exit code) 
function dichotomic_search { 

    min=$1 
    max=$2 
    command=$3 

    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 
}

그것은 반복적으로 사실 반환하는 마지막 값을 찾기 위해 이진 검색을 사용하여 마지막 인자로 주어진 함수를 호출합니다. More explanations on Github

귀하의 경우에는 떠들썩한 배열

통해

이진 검색, 당신은 같이 사용할 것이다 :

#!/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[$2]} | cut -f1 -d :) 
    if [[ "$element" > "$1" ]] 
    then false 
    else true 
    fi 
} 

read target 
highest_index=`expr ${#arr[@]} - 1` 
index=$(dichotomic_search 0 $highest_index "is_smaller $target") 
echo "${arr[$index]}"

출처

2016-12-10 17:56:59 lovasoa

이 솔루션은 오히려 명령의 최초의 성공적인 실행을 위해 찾고있는 것으로 가정 배열의 요소보다

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"

이 항상 명령의 실행이 구성의 절반에 의해 꺼져 @lovasoa 솔루션과는 달리, 성공하는의 첫 값을 인쇄 할 수 있습니다. seq 1 100 | while read o; do SCRIPT; done을 사용하여 유효성을 검사 할 수 있습니다. 여기서 SCRIPT은 위의 알고리즘이며 테스트 된 명령은 test $o -gt $mid입니다.

출처

2017-06-02 11:00:46 OlivierBlanvillain

Bash 스크립트 바이너리 검색

답변

Binary search function in bash

관련 문제