# Thread: studying for exam, have a question!

1. ## studying for exam, have a question!

Im looking over the practice exam our professor put up, and Im having a hard time understanding one of the problems. It goes like this:

Given the following array of character strings,
Code:
```char *list={ "Alpha",
"Bravo",
"Charlie",
"Echo",
"Foxtrot",
"Golf",
"Hotel"};```
In a binary search (where the list is sorted), how many comparisons would be required to determine that the string "Delta" is not in the list? List the strings that would be compared to "Delta" in a standard binary search in the order that the comparisons would be made.

The answer he gives is this:

1.) Echo (element 3)
2.) Bravo (element 1)
3.) Charlie (element 2)

Im having a hard time understanding how he came up with that, can anyone explain it to me? 2. What, according to you should be the answer? Do you know anything about binary search? What have you understood in this question? 3. Originally Posted by BEN10 What, according to you should be the answer? Do you know anything about binary search? What have you understood in this question?
I thought it would go in alphabetical order, so my answer would have been alpha, brave, charlie, then echo. 4. It's not a linear search, it's a binary search where the mid element is taken and searched with "delta", so the list is continuosly divided into two halves. Keep in mind it's not a linear search. For more theory use google for "binary search". 5. Alpha Bravo Charlie |Echo| Foxtrot Golf Hotel
Alpha |Bravo| Charlie
Alpha |Charlie|

why Charlie and not Alpha at the end? or could either one have worked? 6. >> why Charlie and not Alpha at the end? or could either one have worked?

Well, since Bravo < Delta, we know that anything before that will also be less. 7. Work according to this algorithm:
if(low<high)
return -1;
mid=(low+high)/2;
if(x==a[mid])
return mid;
if(x<a[mid])
search for x in a[low] to a[mid-1];
else
search for x in a[mid+1] to a[high]. 8. Originally Posted by BEN10 Work according to this algorithm:
if(low<high)
return -1;
mid=(low+high)/2;
if(x==a[mid])
return mid;
if(x<a[mid])
search for x in a[low] to a[mid-1];
else
search for x in a[mid+1] to a[high].
thank you sir, youve been very helpful  9. Never played "guess a number I'm thinking of between 1 and 10", before?

You cut the difference between 1 and 10, in half, with every guess:

I guess:

5 (secret number is 9) 10/2 = 5

"You're too low"

(Lower limit is now 6, so 10-6= 4 and 4/2 = 2. 6 + 2 = 8

8

"Still too low"
(9 is the new lower limit, 10-9= 1 and 1/2 = 0 with integer division. 9 + 0 = 9)

9

You guessed it.

The upper limit stayed at 10 in this example, but it moves downward, just like the lower limit or floor, moves upward, in the Binary Search.

It seems quite trivial, but with a lot of numbers, it does a fantastic job. It also is the basis for a heuristic we use to solve a lot of programming problems:

Take a big problem, and chop it up successively into smaller one's, and solve them. Finally, you have the whole problem solved. Quicksort is a fine example of this. 10. >> It seems quite trivial, but with a lot of numbers, it does a fantastic job.

Yep. If you're good with juggling numbers in your head it makes a great party trick: "Pick a number between 1 and 1,000,000 and I'll guess the number within 20 tries!". 11. Thanks for detailed help guys  Originally Posted by Sebastiani >> It seems quite trivial, but with a lot of numbers, it does a fantastic job.

Yep. If you're good with juggling numbers in your head it makes a great party trick: "Pick a number between 1 and 1,000,000 and I'll guess the number within 20 tries!".
Crap. there was a true false question about binary searches on the exam that said something along the lines of "on average the number of attempts the algorithm makes are usually half the number of elements in the list". I put true  12. The correct answer is: for a binary search, worst case is log2(N) attempts. If you're lucky it could match earlier than that.

Linear searches average half the number of elements. 13. When you try to find a name in a phone book (archaic concept, I know), do you start at page 1 and start reading down the list until you reach the name?

Or do you use a slightly more intelligent strategy?  14. Originally Posted by wankel Crap. there was a true false question about binary searches on the exam that said something along the lines of "on average the number of attempts the algorithm makes are usually half the number of elements in the list". I put true That is a simple mistake. Half would be a linear search. It may help to look at the complexities of the algorithms
Code:
```linear  = O(n) // data spread randomly
binary = O(log(n)) // data in order```
Now on a linear search, assuming the probably of an element being the one you want is 1/n where n is the size of the list to be search. On average you will find the element by the middle. So you have n/2 searches or half of the list (which is what you said binary search was)

Binary search is a different story. O(log(n)) is much better because a log base 2 of n halves the search space every time. So to search you have to go through log(n) elements in the list. Popular pages Recent additions 