Technical Interview

Home
Technical Interview
Interview Process
Introduction Questions
Quantitative Problems
Google & Microsoft
Algorithms
Object Oriented
C/C++ Questions
Java Questions
Data Structures
Fundamental Questions
Puzzles
Resume Tips
Added Recently
Links
Contact Us
Submit Question/Answer

 

Implement the body of the following function using a binary search of the array. You do not need to check the precondition.   




public static boolean has42(int[ ] data, int start, int end)

    // Precondition: The elements data[start]...data[end] are sorted from smallest

    // to largest. This array segment might be empty (indicated by end being less

    // than start).

    // Postcondition: A true return value indicates that the number 42 appears in

    // data[start]...data[end]. A false return value indicates that 42 doesn’t 

    // appear.
   


 

Solutions:

 

public static boolean has42(int[ ] data, int start, int end)
         {
            int middle;
            
            if (end < start)
               // Empty array segment cannot contain 42.
               return false;
            
            middle = (start + end) / 2;
            else if (data[middle] == 42)
               // We found the number 42.
               return true;
            else if (data[middle] > 42)
               // Continue search of data[start]...data[middle-1].
               return has42(data, start, middle);
             else
               // Continue search of data[middle+1]...data[end].
               return has42(data, middle+1, end);
         }