This is part of a interview question I recently came across and Im not able to find an elegant solution for this. Can someone please help.

Q - We have a non-decreasing sorted array, which is rotated by k indices. Given this rotated array, find the starting index. For example, {1, 2, 1, 1} -> idx = 2

I know that we can fiqure out the start index with different efficient ways but I want to fiqure out what is wrong in my binary search approach.

I came up with the following partially solution which works for most of the cases but fails for corner cases. This may look like an easy solution but it has lot of corner cases. Any help please.

public class bs {
   private int check(int[] nums) {
       int lo = 0, hi = nums.length-1;
       while(lo<hi) {
           int mid = lo + (hi - lo) / 2;
           if((mid==0 && nums[mid]<nums[nums.length-1]) || (mid!=0 && nums[mid]<nums[mid-1])) {
               lo = mid; break;
           } else if (nums[mid] > nums[hi]) {
               lo = mid + 1;
           } else if (nums[mid] < nums[hi]) {
               hi = mid;
           } else if (nums[mid] > nums[lo]) {
               lo = mid + 1;
           } else if (nums[mid] < nums[lo]) {
               hi = mid;
           } else {
               lo++;
           }
       }
       return lo;
   }


   public static void main(String[] args) {
       bs b = new bs();
       System.out.println("Actual :: " + b.check(new int[]{1, 2, 3, 4, 5}) + " Expected :: 0");
       System.out.println("Actual :: " + b.check(new int[]{6, 1, 1, 4, 5}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{1, 2, 1, 1}) + " Expected :: 2");
       System.out.println("Actual :: " + b.check(new int[]{1, 1, 2, 1}) + " Expected :: 3");
       System.out.println("Actual :: " + b.check(new int[]{10, 1, 1, 10}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{2,1}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{4,6,9,9,10,13,13,14,14,14,15,15,15,15,16,16,18,18,19,20,20,22,22,22,24,25,25,27,27,28,28,31,31,33,34,36,36,36,39,40,41,41,42,42,44,47,50,52,53,53,55,55,56,63,63,70,71,72,72,74,76,76,77,79,80,80,80,81,84,84,85,85,88,88,89,89,89,90,91,92,93,93,94,94,94,96,97,97,97,97,98,99,99,100,1,1,1,2,2,4}) + " Expected :: 94");
   }
}

This is part of a interview question I recently came across and Im not able to find an elegant solution for this. Can someone please help.

Q - We have a non-decreasing sorted array, which is rotated by k indices. Given this rotated array, find the starting index. For example, {1, 2, 1, 1} -> idx = 2

I know that we can fiqure out the start index with different efficient ways but I want to fiqure out what is wrong in my binary search approach.

I came up with the following partially solution which works for most of the cases but fails for corner cases. This may look like an easy solution but it has lot of corner cases. Any help please.

public class bs {
   private int check(int[] nums) {
       int lo = 0, hi = nums.length-1;
       while(lo<hi) {
           int mid = lo + (hi - lo) / 2;
           if((mid==0 && nums[mid]<nums[nums.length-1]) || (mid!=0 && nums[mid]<nums[mid-1])) {
               lo = mid; break;
           } else if (nums[mid] > nums[hi]) {
               lo = mid + 1;
           } else if (nums[mid] < nums[hi]) {
               hi = mid;
           } else if (nums[mid] > nums[lo]) {
               lo = mid + 1;
           } else if (nums[mid] < nums[lo]) {
               hi = mid;
           } else {
               lo++;
           }
       }
       return lo;
   }


   public static void main(String[] args) {
       bs b = new bs();
       System.out.println("Actual :: " + b.check(new int[]{1, 2, 3, 4, 5}) + " Expected :: 0");
       System.out.println("Actual :: " + b.check(new int[]{6, 1, 1, 4, 5}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{1, 2, 1, 1}) + " Expected :: 2");
       System.out.println("Actual :: " + b.check(new int[]{1, 1, 2, 1}) + " Expected :: 3");
       System.out.println("Actual :: " + b.check(new int[]{10, 1, 1, 10}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{2,1}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{4,6,9,9,10,13,13,14,14,14,15,15,15,15,16,16,18,18,19,20,20,22,22,22,24,25,25,27,27,28,28,31,31,33,34,36,36,36,39,40,41,41,42,42,44,47,50,52,53,53,55,55,56,63,63,70,71,72,72,74,76,76,77,79,80,80,80,81,84,84,85,85,88,88,89,89,89,90,91,92,93,93,94,94,94,96,97,97,97,97,98,99,99,100,1,1,1,2,2,4}) + " Expected :: 94");
   }
}

• algorithm
• binary-search

• 1 It is not possible with binary search. – n. m. could be an AI Commented Mar 31 at 6:04
• 2 Note that any correct solution will have to support, in the worst case, examining every element. (For example: suppose I tell you upfront that every element is 1 except for a single 2. You have to find that 2 in order to return the right answer; but the only way to find it is to examine every element, in some order, until you come across it.) So although you can use binary search to optimize the common case, pure binary search can't cover all cases. – ruakh Commented Mar 31 at 7:53

2 Answers 2

There are two issues in your implementation:

1. In the case where you evaluate nums[mid] > nums[lo] as true, it is wrong to set lo = mid + 1. By the just-checked condition it is certain that nums[lo] is a candidate, and by updating lo as you do, you exclude it from the lo-hi window. In fact, because of the earlier conditions that were already checked it is at this point sure that the index to return is lo, so you should instead break out of the loop in this case.

2. In the final else case it is wrong to do lo++. When we arrive in this case the previously checked conditions guarantee the values at lo, mid and hi are all the same: if we had previously encountered another (distinct) value (necessarily a greater one), then certainly lo would be the index to return, and so lo++ misses that opportunity. If however, we had not yet encountered any other (greater) value before getting here, we really have no clue where to continue the search as the searched index could well be less than, equal to or greater than the current mid index.

   If you really want to stick with the binary search approach, then one thing you could do is to perform the binary search at both sides. This also means the worst-case time complexity becomes O(