The binary search in your code is the cause I guess…
Even I had same problem with my code, when there is repetition of numbers in the array, binary search may give you an index between the range of indices of that number…
we can eleminate the cases of 1 , 2 , 3 ,4 and use binary serach for other numbers which will reduce your complexity to nlogn
I have thoroughly checked my binary search. Repetitions have been handled properly. And I could not understand " binary search may give you an index between the range of indices of that number"…
@atulsehgal: Please give a test case which fails my code…??
@djdolls : Please look into my code…