current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.3 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote -1 down vote favorite

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
share|improve this question
    
Do you understand the idea behind how a binary search is set up? Could you do it step by step on paper, for example? – Kon Jul 16 '13 at 0:18
1  
Where does this problem come from? There is a version at: emp.byui.edu/olavesonm/cit352/a10.htm – Ciro Santilli 烏坎事件2016六四事件 法轮功 Nov 22 '15 at 10:19
up vote 2 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.