binary search questions help

[compscidummy]

Hi! Could someone please help me with the following binary search questions? (explain please!) Thanks.

A binary serach will be performed on the following list:

4, 7, 9, 11, 20, 24, 30, 41

1. To find the key value 27, the search interval after the first pass through the loop will be?

2. How many iterations will be required to determine that 27 is not on the list?

3. For which set of data will a sequential search perform more efficently than a binary search, if the value being searched for is 5?

a. 4, 5, 6, 8, 9, 11
b. 1, 2, 4, 5, 7, 10
c. 2, 4, 6, 8, 10, 12
d. 1, 2, 3, 4, 5, 6
e. 0, 1, 2, 3, 4, 5

[Ganon11]

Do you know the concept of a binary search?

Have you possibly seen a Java implementation of the binary search (maybe in a textbook you're using)?

[compscidummy]

Do you know the concept of a binary search?

Have you possibly seen a Java implementation of the binary search (maybe in a textbook you're using)?

I just begun doing it in class today but I don't understand it at all.....

yes I've seen an implementation but it doesn't make much sense to me.

[Nepomuk]

OK, let's see.

You have some values given. If you want to put them in a binary tree, you'll have to decide, how to sort them.

Now, what does a binary tree look like? Here are two little pictures:

        O
      /   \
    O       O
   / \     / \
  O   O   L   O
 / \ / \     / \
L  L L  L    L  L
 

          O
        /   \
      O       L
     / \     
    O   L
   / \
  O   L
 / \
L   L
 

Now, every O is an inner knot and every L is a leaf. As you see, not all leaves must have the same distance from the root knot.

What is the big difference between those two trees I drew? (Apart from the amount of knots that is.) Right, the first one is more balanced. Balanced trees are very good for searching while the second possibility is easy to remove knots from.

OK, now these are just a general binary trees. There are different sorts however. First of all, you can differ between leaf based saving (values are saved only in leaves) and knot based saving (values are saved in inner knots only). Both types of binary trees have their advantages.

If you want to use such a tree efficiently, you organise it in such a way that for every subtree with the root T:

  T
 / \
L   R
 

and L and R being subtrees, the following are valid:

• All values in L are smaller than the value in T
• All values in R are greater than the value in T

So, how would you sort those numbers in such a tree?

Oh, and let's assume you save your values in the knots. When do you know, that a value isn't in the tree?

Greetings,
Nepomuk