Leetcode 33: search in rotated sorted array

March 26, 2020

Introduction

It is the first time I tried to write the code while the interviewee worked on his coding. I wrote a solution to search in rotated sorted array. I like my experience as an interviewer, and also I try to master the algorithm through being a responsible interviewer.

My solution and sharing

Here is my discussion post.

March 25, 2020
It is the algorithm I like to learn from mock interviews as an interviewer. I also wrote the code while I interviewed the interviewee using the algorithm.

Case study
How to develop a working solution to solve the problem? The analytics skills are very important, as an interviewer, I like to judge if the interviewee can analyze the binary search algorithm using his/ her own words.

It is trivial to search a target value in sorted array. But if the sorted array is rotated, then it is more challenge but it can be still solved using modified binary search.

Let me work on two test cases through failed test cases written by the interviewee on March 26, 2020. Here is the blog with a case study of mock interview.

case study 1:
{4,5,6,7,0,1,2}, 6
In order to find value 6, we have to consider how to apply modified binary search.
Middle index position is 3, value is 7. So left half is [0,3), and right half is (3, 6].
The left half's two edge node's value is 4 and 7, and since 4 < 7, it is in ascending order, 6 is in the range of [4,7). So binary search every step is to get rid of half of numbers, so the search can be narrowed down to left half.

case study 2:
{4,5,6,7,8,1,2,3}, 8
In order to to find value 8, the middle index value is 3, middle value is 7, left half is [0, 3), both end values 4 and 7 are less than 7, since left half is in ascending order, 7 cannot be in left half.

Argument
The argument should be reviewed and be proved correct first before the interviewee writes his code.

My argument is if the range is in ascending order, then the target can be determined if it is in the range or not. The condition is target >= startValue && target <= endValue, [startValue, endValue] are two values of the range.

But one of the interviewee's argument is that the range with [startValue, endValue], startValue > target, endValue > target, then target is not in the range. It is not correct!

Here are highlights for me to work on online judge to pass all test cases:

1. Declare an explanation variable firstHalfAscending, edge case left half only has one node;
2. If first half is in ascending order, and also target is in the range, then remove right half, otherwise reove left half;
3. My argument is at least one half is in ascending order
4. If step 2 is not true, then right half should be in ascending order, copy and paste the if/ else part, change range from [start, middle) to (middle, end].
5. In order to expedite the coding, also bug-free, I need to test the code by myself instead relying on leetcode online judge.

public class Solution {
    public int Search(int[] numbers, int target) {
        if(numbers == null || numbers.Length == 0)
            return -1; 
        
        var length = numbers.Length; 
        int start = 0; 
        int end = length - 1; 
        while(start <= end)
        {
            var middle = start + (end - start)/2 ; 
            var middleValue = numbers[middle];
            
            if(middleValue == target)
            {
                return middle; 
            }
            
            var firstHalfAscending = middleValue >= numbers[start];
            if(firstHalfAscending)
            {   // in range 
                if(target >= numbers[start] && target < middleValue)
                {
                    // remove right half
                    end = middle - 1; 
                }
                else
                {
                    start = middle + 1; 
                }
            }
            else 
            {
                // in range 
                if(target > middleValue && target <= numbers[end])
                {
                    // remove left half
                    start = middle + 1; 
                }
                else
                {
                    end = middle - 1; 
                }
            }                       
        }
        
        return -1; 
    }
}