33. Search in Rotated Sorted Array

August 22, 2019

Introduction

It is my favorite binary search algorithm. I practiced so many times on binary search algorithm, and today I like to practice one more solution, and start to work on show case how to solve a binary search algorithm quickly and also bug-free. I overestimated myself and wrote a few bugs recently on one of onsite interview, and I did not listen to fix the bug to try more test cases.

One more practice 

Here are the blogs I wrote related to Search in rotated sorted array in 2017.

Here is the post I wrote today.

C# modified binary search practice on August 22, 2019

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

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
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.

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
3. 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 in 2017.

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];
    }
}