The binary search algorithm - would my implementation be acceptable in a job interview ?

[Andy Jack]

I tested the code i made with many test inputs. It seems to be working perfectly. Its much longer, but would it be acceptable to you were an interviewer and I did it like this in a Job Interview ?

One - Made by me

    public int search(int toFind)
    {	
    	//we search myArray for a number	
    	int foundAt = -1;//-1 means that the number you were looking for was not found
    	int arrayLength = myArray.length;
    	int lastIndex = arrayLength - 1;
    	
    	//If array is not sorted, then don't search
    	if(isSorted == false)
    	{
    		System.out.println("Cannot search until the array is not sorted.");
    		return foundAt;
    	}
    	
    	
    	//If array size is 1, then don't use algorithm. 
    	if(arrayLength == 1)
    	{
    		foundAt = (myArray[0] == toFind)? 0:-1;
    		return foundAt;
    		
    	}
    	
    	
    	/*If element toFind > last element of array, then we get out of bounds error.
    	 * To prevent that, check that condition with an if
    	*/
    	
    	if(toFind > myArray[lastIndex])
    	{
    		foundAt = -1;//Can avoid this line, but be safe
    		return foundAt;
    	}
    	
    	
    	//Binary Search Algorithm
    	int start = 0;//start and end is the range of indexes in which we are currently searching
    	int end = lastIndex;
    	int mid = -1;//middle of segment of array under consideration  
    	
    	while(start != mid)
    	{
    		mid = start + (end-start)/2;
   
    		if(myArray[mid] == toFind)
    		{
    			foundAt = mid;
    		    return foundAt;	
    		}
    		
    		if(myArray[mid] > toFind)
    		{
    			end = mid - 1;//Start remains fixed
    		}else
    		{
    			start = mid + 1;//End remains fixed
    		}
    		
    	}
    	
    	return foundAt;
    }

Two -

   public int find(long searchKey)
      {
      int lowerBound = 0;
      int upperBound = nElems-1;
      int curIn;

      while(true)
         {
         curIn = (lowerBound + upperBound ) / 2;
         if(a[curIn]==searchKey)
            return curIn;              // found it
         else if(lowerBound > upperBound)
            return nElems;             // can't find it
         else                          // divide range
            {
            if(a[curIn] < searchKey)
               lowerBound = curIn + 1; // it's in upper half
            else
               upperBound = curIn - 1; // it's in lower half
            }  // end else divide range
         }  
      }  

[Anayonkar Shivalkar]

Hi Andy,

Logic wise, I don't see anything odd in your code.

However, if I were the interviewer, I would ask below questions:
1) How are you getting value of isSorted? That is - how are you deciding that the array is sorted? And more importantly, why are you deciding it? By default, binary search works only on sorted arrays; and deciding if an array is sorted or not might take more time in case of very large arrays.
2) Just like you are having condition 'toFind > myArray[lastIndex]', why there is not other condition (toFind < myArray[0])?

Point 2 is not a big deal, but for point 1: I wouldn't check the 'orderness' of an array unless explicitly asked. Yes, you may get wrong output if you provide an unsorted array(that is - wrong input), but that is known limitation of binary search. YMMV.

HIH.

[fred rosenberger]

There's really no reason to ever do

if (boolean == false)

just do

if (!boolean)

or

if (boolean)

[Andy Jack]

Anayonkar Shivalkar wrote:Hi Andy,

Logic wise, I don't see anything odd in your code.

However, if I were the interviewer, I would ask below questions:
1) How are you getting value of isSorted? That is - how are you deciding that the array is sorted? And more importantly, why are you deciding it? By default, binary search works only on sorted arrays; and deciding if an array is sorted or not might take more time in case of very large arrays.

Hey Fred ! Thanks for taking the time to review my clunky code . I appreciate it very much.

I did not show the sort method which sets the boolean class member isSorted = true once it does the sorting. Since search(int) is public, i don't want to get an error if the user of the class calls search before sort accidentally.

[Andy Jack]

fred rosenberger wrote:There's really no reason to ever do

if (boolean == false)

I am not able to understand why we should not do that ?

[Pat Farrell]

Andy Jack wrote:

if (boolean == false)

I am not able to understand why we should not do that ?

Its very clearly bad style. If you want to test a boolean, test it. if (!boolean)

omit unnecessary words.

Performance-wise, the compiler or the JIT optimizer will implement it as if it were if (!boolean) anyway.

[Pat Farrell]

If I were asking the question, I'd expect you to not write a binary search algorithm, but rather to use one of the Java Collections framework structures. The Collections framework are robust, fast, and well tested.

The goal should not be to re-write the wheel, but to pick the right wheel and use it.

[Andy Jack]

Pat Farrell wrote:If I were asking the question, I'd expect you to not write a binary search algorithm, but rather to use one of the Java Collections framework structures. The Collections framework are robust, fast, and well tested.

The goal should not be to re-write the wheel, but to pick the right wheel and use it.

I strongly disagree. I feel that one must first know the basics and then use these tools or frameworks. Make your own code
and compare it with the efficient ones - reveal the flaws in your own thinking. Patch those flaws.
To me, it seems that a solid foundation in DS and Algo is a must for being a developer and also for job interviews.

[Pat Farrell]

The fundamental point of Object Oriented Programming is to encourage, and if possible, force, code reuse. The Collections exist. Use them. Re-implementing them takes time better spent on the domain problems.

Now, if the job interview was for the Google Guava team, I'd have a different answer. But for a typical IT professional job, do-it-yourself is really replicate-existing-work.

[Mike Simmons]

I think being well-grounded in algorithms is a good thing, and it can indeed help in interviews (often more than it helps in the actual job). That said, in any job interview I would first give an answer based on efficient use of existing libraries. If the interviewer is really interested in seeing how well you can code something from scratch, and wants to use an algorithm question to do it, fine - they can guide the interview that way easily enough, and you can show your stuff then. But I would definitely recommend against taking a do-it-yourself approach from the beginning. Many interviewers will take that as a sign that you'll waste time reinventing the wheel, rather than getting on with more productive work.

[Anayonkar Shivalkar]

Andy Jack wrote:

fred rosenberger wrote:There's really no reason to ever do

if (boolean == false)

I am not able to understand why we should not do that ?

I missed this

The main reason you are not supposed to do this is - if by mistake you write something like:

if(isSorted = false)

the code will compile, and will assign false value to isSorted (needless to say, it will never enter inside 'if' condition).

Also, as Pat and Mike has mentioned, you need to understand requirements first. If the interviewer is testing your knowledge of existing APIs, then you are supposed to make use of existing methods (instead of writing your own code).

[Andy Jack]

Anayonkar Shivalkar wrote:

Andy Jack wrote:

fred rosenberger wrote:There's really no reason to ever do

if (boolean == false)

I am not able to understand why we should not do that ?

I missed this

The main reason you are not supposed to do this is - if by mistake you write something like:

if(isSorted = false)

the code will compile, and will assign false value to isSorted (needless to say, it will never enter inside 'if' condition).

Now I remember. That is exactly what I had done in the above code. No wonder my code was not working properly.

[Andy Jack]

This is what the class looks like -

public class OrderedArray {
	
	//ASSUMPTION - NO elements in array are repeated  
    private int [] myArray = null;   
    private boolean isSorted = false;  
  
    
    OrderedArray(int [] givenArray)  
    {  
    	
        if(givenArray == null)
        {
        	sopln("\nThe given array is null ! Cannot sort a null array !");  
        	sopln("Please create a new valid array"); 
            return;  
        }
        
        int length = givenArray.length;  
        myArray = new int[length];  
        for(int i = 0; i < length; i++ )  
        {  
            myArray[i] = givenArray[i];  
        }  
               
        this.insertionSort();//choose your sort method here
          
    }  
  
    
    public static void main(String[]args)
    {
    	int[]nums = {8,3,7,4,11,2,6,9,19};
    	OrderedArray oaDemo = new OrderedArray(nums);
    	sopln("");
    	oaDemo.printArray();
    	int foundAt = oaDemo.binarySearch(6);
    	sopln("Found At " + foundAt);
    	
    }
    
    
    private void bubbleSort()
    {
        if(myArray == null)
        {
        	sopln("\nThe array is null ! Cannot sort a null array");  
            return;  
        }  
    	
        int temp = 0;
        //BubbleSort Algorithm
        
        //Decides the range for inner loop
        for(int range = myArray.length-1 ; range >= 0 ; --range)
        {
        	for(int j = 0; j < range ; j++)
        	{
        		if(myArray[j] > myArray[j+1])
        		{
        			temp = myArray[j];
        			myArray[j] = myArray[j+1];
        			myArray[j+1] = temp;		
        		} 
        		
        	} 
        	
        }
         
        isSorted = true;
        
    }
    
    //Selection sort algorithm
    private void selectionSort()
    {
    	if(myArray == null)
        {
    		sopln("\nThe array is null ! Cannot sort a null array");  
            return;  
        }  
    	
    	int smallestAt = 0;//Assumed
    	int arrLength = myArray.length;
    	int  temp = 0;

    	//Range under consideration
    	for(int i = 0; i < arrLength; i++)
    	{
    		
    		smallestAt = i;
    		
    		//Loop through current range
    		for(int j = i + 1 ; j < arrLength; j++)
    		{
    			if(myArray[j] < myArray[smallestAt])
    			{
    				smallestAt = j;//Note the position with the smaller number

    			}
    			
    		}//Smallest number in current range found.
    		
    		//Swap int in current smallest with int at i, ie start of range
    		temp = myArray[i];
    		myArray[i] = myArray[smallestAt];
    		myArray[smallestAt] = temp;
    		
    	}
    		
    	isSorted = true;

    }
    
    
    private void insertionSort()  
    {  
    	//Algorithm - Insertion Sort 
          
        if(myArray == null)
        {
        	sopln("\nThe array is null ! Cannot sort a null array");  
            return;  
        }  
        
        int temp = 0;//Temporary storage
        
        for(int i = 1; i < myArray.length; i++)
        {
        	temp = myArray[i];
        	int j; 
        

        	for(j = 0 ;   myArray[i] > myArray[j] ; j++)
        	{	
        		//Do nothing, just loop  
        	}
        	
        	
        	//Note this value of j and shift all digits between j and i-1 to the right, by one position
			for(int k = i-1; k >= j; k--)
			{
				myArray[k+1] = myArray[k];
			}
			
			myArray[j] = temp;
        	
        }
          
        isSorted = true;
        
    }  
    
    
    //Search
    private int binarySearch(int toFind)
    {	
    	//we search myArray for a number	
    	int foundAt = -1;//-1 means that the number you were looking for was not found
    	int arrayLength = myArray.length;
    	int lastIndex = arrayLength - 1;
    	
    	//If array is not sorted, then don't search
    	if(isSorted == false)
    	{
    		sopln("Cannot search until the array is not sorted.");
    		return foundAt;
    	}
    	
    	
    	//If array size is 1, then don't use algorithm. 
    	if(arrayLength == 1)
    	{
    		foundAt = (myArray[0] == toFind)? 0:-1;
    		return foundAt;
    		
    	}
    	
    	
    	/*If element toFind > last element of array, then we get out of bounds error.
    	 * To prevent that, check that condition with an if
    	*/
    	
    	if(toFind > myArray[lastIndex])
    	{
    		foundAt = -1;
    		return foundAt;
    	}
    	
    	
    	//Binary Search Algorithm
    	int start = 0;//start and end is the range of indexes in which we are currently searching
    	int end = lastIndex;
    	int mid = -1;//middle of segment of array under consideration  
    	
    	while(start != mid)
    	{
    		mid = start + (end-start)/2;
    		
    		if(myArray[mid] == toFind)
    		{
    			foundAt = mid;
    		    return foundAt;	
    		}
    		
    		if(myArray[mid] > toFind)
    		{
    			end = mid - 1;//Start remains fixed
    		}else
    		{
    			start = mid + 1;//End remains fixed
    		}
    
    		
    	}
    	
    	return foundAt;
    }
      
      
    public void printArray()  
    {  
        if(myArray == null)
        {
        	sopln("\nThe array is null ! Cannot print a null array");  
            return;  
        } 
        
        for(int i : this.myArray){sop(i + ", ");}  
        sopln("");
        
    }  

    
    public static void printArray(int[] array)  
    {  
    	if(array == null)
        {
    		sopln("\nThe array is null ! Cannot print a null array");  
            return;  
        } 
    	
        for(int i : array){sop(i + ", ");}  
        sopln("");
        
    } 
    
    
    private static void sopln(String toPrintLn)
    {
    	System.out.println(toPrintLn);
    }
    
    private static void sop(String toPrint)
    {
    	System.out.print(toPrint);
    }
    

}