How to do in-memory binary search in Bash?

Question

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

Given that Bash has associative arrays, you'd normally do this with an array indexed by name containing the corresponding grade. That doesn't require a binary search. Given that you need to do a binary search, one way to do it is to create parallel arrays indexed by numbers, one for names, the other for the matching grade. You then do a binary search for the name in the names array, recording the index at which you find the name; you use that index to find the grade. Remember that Alice, Evelyn and Mallory are not in the list, so you must handle names that are missing. — Jonathan Leffler, Feb 27 '14 at 01:02
There are lots of places where you can find a binary search algorithm to hunt through an array of names with index range 0..N-1 (for N names in the array). — Jonathan Leffler, Feb 27 '14 at 01:04

score 2 · Answer 1 · answered Feb 27 '14 at 01:42

Every one here wants you to learn this stuff rather than do the assignment for you so I'm intentionally being a little obtuse.

And keep in mind any solution proposed here is how that one programmer would do it, not necessarily the ONE TRUE way.

You need to first get your grades into your program - start with that. Each line in the file is a student name separated from a grade by a ":". You want to read those into two parallel arrays (As Jonathan pointed out).

If you google for 'bash split string' you will find lots of helpful advice on how to do this. I did it this way to get two arrays, one holding the student name and the other holding the grade.

((i=0))
while IFS=":" read -a fields ;
do
    students[$i]=${fields[0]}
    grades[$i]=${fields[1]}

    ((i++))
done < students.dat
echo ${students[@]}
echo ${grades[@]}

Cool! Now you need to work on the binary search algorithm a little. Remember you can get the length of an array with ${#ArrayName[@]}

Since the list is apparently already sorted you won't have to do that yourself so you can comparing the name you want to the student name at the midpoint of the array. If the student name you are looking for is greater than the student name at the midpoint, then you know the one you want is in the latter half of the array, and vice versa. Eventually the student name at the midpoint will be exactly the one you are looking for.

score 1 · Answer 2 · answered Feb 27 '14 at 01:06

If it doesn't have to be in bash then you can use awk for it. bash only started associative arrays in version 4, so portability might be something you'll need to think about.

Disregard the solution if awk is not an option available to you:

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

Test:

$ 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

Yea sadly it has to be a bash script. – Jacob Holman Feb 27 '14 at 01:10 — Jacob Holman, Feb 27 '14 at 01:10

score 1 · Accepted Answer · answered Nov 13 '14 at 17:16

Here Is a working binary search bash script for those students still searching.

  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
 }

This does not find e.g. 4th element of 6 element sorted unique element array. END is set wrong way in the loop. — jarno, Dec 10 '16 at 08:58

How to do in-memory binary search in Bash?

3 Answers3

Test:

Linked