CareerCup

Because it is a straight Binary Search question which is basic algorithm that first year students study in their college and a company of eBay's repute asking it, without any twist in words or twist in application of binary search.

So, I was shocked.

I was asked binary search at Amazon. I didn't get the code 100% correct, but I was still the best the interviewer had ever seen on this question.

Binary search is trickier than one might think. Nitin, try this: do it yourself, with a time limit of 15 minutes (all while spending time explaining aloud what you're doing), without looking at a computer or testing your code other than by hand. Then post your code here.

There are some very subtle problems that you can have. For instance, what do you think of this method of finding the midpoint? int mid = (l+r)/2; Looks correct?

@Gayle: was your mistake limited to int mid = (low + high) / 2? In my opinion that one's barely a real mistake...

Ya it is integer overflow case.

Instead one should do like

low + (high - low) / 2

Yes, Ebay asked this question for the position of Junior Java Developer. Can anyone suggest me if the code below is okay? It works fine but I was wondering since someone mentioned the "mid" problem I was hoping I could use some insight. Thank you. Here's the code:

static int [] arr={1,2,3,5,6,7};
	
static int input=5;

int head1=0;

int tail1=arr.length-1;
int mid1=((tail1-head1)/2);
		
binaryRecursively(mid1);

binaryRecursively(int mid) {
	if (arr[mid]==input){
		System.out.println("Found Recursively - "+arr[mid] +" at index - "+mid);
	}
	else if (arr[mid]<input){
		mid++;
		binaryRecursively(mid);
	}
	else if (arr[mid]>input){
		mid--;
		binaryRecursively(mid);
	}
		
}

@Nitin: well, there are a couple possibilities here:

1) You just happen to be considerably more attentive to detail than almost everyone else. I believe I made the integer overflow mistake the first time I attempted this problem in a time-sensitive setting, before I knew to watch for that issue.
2) You've read about the gotchas of this problem before -- other candidates may only understand the concept, without remembering small details like not falling into the kind of trap you just avoided.
3) You might have missed the overflow issue if I hadn't remarked on it, if you had been not scrutinizing that line in particular.
4) You might have avoided that mistake, but made a different mistake if you were attempting this problem under time and social pressure.

@eugene.yaravoi :- In my initial days, I never cared about integer overflow condition. My sole purpose used to be just solve the problem. So, yes I also had made this mistake in my college days. But, later on, I learned that overflow cases can occur. So, now I've become more attentive on these kind of details also.

@ gunsnroses23k :- You should never calculate mid like above.

Consider a scenario where low = 5, high = 7.
Note that these are numerals above are representing index of array not elements of array.

Ideally - our mid should be index no 6
But according to your code, it would be 1, which is wrong.
Now you can calculate mid like this

mid = (low + high) / 2

You will get correct answer which is 6. But this can fail when the sum of low and high exceeds the integer limit defined for that data type in that language.

So, the correct way is

mid = low + (high - low) / 2

@ nitin Thanks for the input. I agree with your suggestion but if you look carefully what I did was not exactly binary search. I would rather call it a distorted form of binary search. The performance in my program can be slow but it does work as according to my code "high" & "low" are always constant & recursive method is invoked with argument of "mid" which is either just incremented or decremented (as I said this can be a lot slower than binary search for large arrays but it does work) The reason I did that was because I wanted to show them something different than what usually they would expect anyway if asked next time I would keep all that in my mind including the integer overflow case. Thanks for the help!

Coding binary search correctly is not as easy as Nitin Gupta puts it. IMO, he already knows it, so is unable to see why it might be a reasonable quesiton to ask. Also, even if it was an easy question, what is the harm in asking it? There are a lot of followup questions one can ask. For instance, does the code work if there are duplicates? Can you modify it to return the first occurence? Can you suggest some optimizations? etc etc.

low=a[0] is wrong should be low=0

mid can go forever if the value you are searching for is not in the array. so i would pass the max and min to validate if mid is not going beyond possible array index value.

else return -1 (or whatever value you use to indicated not found)