Binary search theory questions

[HG319]

Imagine you have 101 dalmatians and that no two dalmatians have the same number of spots. Suppose that you create an array of 101 integers: the first integer is the number of spots on the first dalmatian, the second integer is the number of spots on the second dalmatian, and so on. Your friend wants to know whether you a dalmatian with 99 spots. Thus you need to determine whether your array contains the integer 99.

a. if you plan to use a binary search to look for the 99, what, if anything would you do to the array before searching it?
b. What is the index of the integer in the array that a binary search would examine first?
c. If all you dalmatians have more than 99 spots, exactly how many comparisons will binary search require to determine that 99 is not in the array?

for answer a, I would think to sort the array, but I am not sure if that is allowed because it says he first integer is the number of spots on the first dalmatian, the second integer is the number of spots on the second dalmatian, and so on.

for answer b, I thought you should split the array in half like I did in the search function, so I guess start with the middle index.

for answer c, would this be 50 comparisons?

Even though these answers do not need code I just want to show you that I thought about this

  int main(){
    int spot_array[101];
    int size=101;
    //sends to a function to enter the spots of the dalmatians
    binarySearch(99);
    

system("Pause");
return 0;
}

void binarySearch(int spots[], int size, int key )
{
       int position;
       int comparisonCount = 1;    //count the number of comparisons 
       int lowerbound=0, upperbound 100;
       position = ( lowerbound + upperbound) / 2;

       while((array[position] != key) && (lowerbound <= upperbound))
       {
              comparisonCount++;
              if (array[position] > key)              
             {                                                 
                    upperbound = position - 1;    
             }                                                      
             else                                                
            {                                                        
                   lowerbound = position + 1;     
             }
             position = (lowerbound + upperbound) / 2;
       }
      if (lowerbound < = upperbound)
      {
            cout<< "The number was found in array subscript "<< position<<endl<<endl; 
            cout<< "The binary search found the number after " << comparisonCount 
                   << " comparisons.\n";              
            // printing the number of comparisons 
       }      
       else
             cout<< "Sorry, the number is not in this array.  The binary search made "
                   <<comparisonCount << " comparisons.";
       return;  
} 

[LB]

You are correct for part A: you would call std::sort.
You are correct for part B.
For part C, though, you forget that binary search has a logarithmic complexity. Each time you fail to find what you are looking for, the playing field is halved.

[HG319]

Thanks LB, can you explain what I would need to do for part c?

[Bdanielz]

It looks like they are just asking a question?

c. If all you dalmatians have more than 99 spots, exactly how many comparisons will binary search require to determine that 99 is not in the array?

A Binary search is (log2 n).

can you explain what I would need to do for part c?

Below is a table that shows n comparisons to search space.

http://zebu.uoregon.edu/2000/ph199/bits2.gif

Assuming you just need to answer a question then that table should answer your question.

[Militie]

When you are searching for a variable with binary search, half of the variables you have are eliminated from the search every time you go through.

What the search does is goes to the half way point of the elements, checks if the element you are looking for is smaller of larger than the element at the halfway point and eliminates the half that the element could not exist in, during the next search.

Searching for 3:

Okay, now I take the number of the lowerbound (1) + the upper bound (13) and divide by two, now I get 7

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)

Well, I (the code) know that 3 is less than 7, so everything over 7 , I don't even need to look at now.

(1)(2)(3)(4)(5)(6)

Okay, now I take the number of the lowerbound (1) + the upper bound (6) = 7, then divide by two. (Integer division gives me 3, I truncate the decimal off the 3.5) Now I have three. Hey! Look at that, 3 is my answer, now I am done.

(3)

This is how a binary search works, it eleminaties half of the elements in the search every time it goes through. This is why a binary search has a log. (base 2) search for however many numbers you have.

So log₂99 = Your answer for C.

[HG319]

would it just be 7 comparisons?