33. Search in Rotated Sorted Array

C# modified binary search practice on August 22, 2019

Here is the link. 

It is most challenging solution to write. The idea is based on the argument that there is only at most one pivot value in the array ( the pivot value is bigger than left one and right one), at least one range is in ascending order. I should use the ascending range to determine which half should be get rid of. Do not say that only in important onsite interview, use an example to explain the idea as well.

Case study 1

I believe that it is important to do a case study, explain the idea using the test case. So interviewer and interviewee can both understand the algorithm. It is important to explain using concrete test case, go through the test case to explain how to find the solution.

Given a rotated sorted array [4, 5, 6, 7, 0, 1, 2}, target = 0.
start = 0, end = 6,
middle = start + (end - start)/ 2 = 3, so binary search should divide range into two using index = 3.
We like to look into two ranges, first one is Range 1: [4, 5, 6, 7], and then second one is Range 2: [7, 0, 1, 2]
We know that at least one of ranges is in ascending order, since at most one pivot value in the array.
For example, [4, 5, 6, 7, 0, 1, 2], the pivot value is 7, index = 3, which is bigger than left one, 6; also bigger than right one 0.

Range 2: [7, 0, 1, 2] is not in ascending order, but Range 1: [4, 5, 6, 7] is. I can use the Range 1 to get rid of half numbers in search, since 0 is not in range, so Range 1 can be removed in search.

Case study 2
I like to write a case study on [3, 1], target = 1.
So first search, start = 0, end = 1;
middle = 0;
middle index position divides the array into two ranges.
First one is [start, middle], [0,0], only one node in the range.
Second one is [middle, end], [0, 1], two nodes in the range.
We always take one node range is ascending.
So numbers[0] = 3, comparing to target 1, which is not in the range.
Binary search will move to range [1,1].

apply middle calculation again, middle = 1;
Two ranges, one is [1,1], second one is [1,1].
numbers[1] == target, find the value.

Common mistakes

Common mistakes of binary search is my favorite research topic. I like to figure out how to find more to list in the following:

1. Index-out-range error
2. One number in search range, range not existing
3. Time limit exceeded
4. Missing cases in analysis

Advice:

1. Always work on middle and value on middle index;
2. Be careful about index-out-range error, do not assume that middle -1 or middle + 1 is in range of numbers array;
3. Double check basic logic checking;
4. The algorithm is the best algorithm for onsite or mock interview; Since it is easy to write code with index-out-of-range, timeout bug etc.
5. Work hard on common mistakes in binary search. I wrote one blog on this topic back in 2017. I should continue to work on this topic.

Drills

To train myself to write executable code in 20 minutes interview, I like to come out some drills for me to practice.

1. Test case [3, 1], target 1, see if return value 1 instead of -1;
2. More will be added here later.

public class Solution {
    /// modified binary search 
    public int Search(int[] numbers, int target) {
        if(numbers == null ||  numbers.Length == 0)
            return -1; 
        
        var start = 0; 
        var end   = numbers.Length - 1; 
        
        while(start <= end)
        {
            var middle = start + (end - start)/ 2; 
            var middleValue = numbers[middle];
            
            if(middleValue == target)
                return middle;                                             
   
   // Do not consider middle - 1 or middle + 1, which may be out of range of numbers array
            // two range [start, middle], [middle, end]
            // range can be one value only           
            var leftAsc    = middleValue   >= numbers[start] ;
            var rightAsc = numbers[end] >= middleValue; 
            
            if(leftAsc)
            {
               if (isInRange(target, new int[]{numbers[start], middleValue}))
               {
                   end = middle - 1; 
               }
               else 
               {
                   start = middle + 1; 
               }
            }
            else if(rightAsc)
            {
                if (isInRange(target, new int[]{middleValue, numbers[end]}))
               {
                   start = middle + 1; 
               }
               else 
               {
                   end = middle - 1; 
               }
            }           
        }
               
        return -1;         
    }
               
    private static bool isInRange(int target, int[] range)
    {
        return target >= range[0] && target <= range[1];
    }
}

C# various practices in 2019, here is the link.