Leetcode 33: Search in sorted rotated array

Nov. 24, 2017

Introduction

Sometimes I have to push myself to be a good thinker instead of being a programmer, just think, no play with debugger, mock interview test cases, Leetcode online judge. I should think about basics by myself, for example, when I write depth first search, I should put base case first, evaluate edge case and leave it to myself, do not let Leetcode online judge remind me missing edge case.

Today I learn that Leetcode 33 online judge is a better tool, my two practice of the following neither passes the test case with given array [1, 3] and search value 3. 

I made two code reviews after Nov. 22 mock interview, both of them are buggy code. I found the issue through Leetcode 33 online judge later on. The following two sections are included with the detail.

Code review 1

Plan to spend 30 minutes to play with logic, Work with the conditions:

Here are my thoughts in plain English.

I like to make the code short and then I have more time to explain my idea in mock interview.

First argument:
Only check first half and see if the number is in the first half or not.

Assuming that the first half is in ascending order, then the number to search should be in the range of start and end value, otherwise the first half is not in ascending order, then start value is bigger than middle value. We can infer that second half range is in middle value to start value. We just need to make sure that search number is not in the second half range.

Here is the C# code passing all test cases. But actually the code has a bug by going through Leetcode 33 online judge.

I reviewed the code and found out that I break DRY - do not repeat yourself principal.

By going through the following logic, I found out that the logic can be simplified, need to get rid of checking called firstHalfAscending, but the code is wrong for second part circled in red color. It should be || not &&.

Actually the mock interview tool does not have good test cases, leetcode 33 online judge shows that the above code has failed test case, [5, 1, 3], 5

If the first half is not in ascending order, the logic checking is || not &&.

search >= startValue || search < middleValue

Code review 2

No more code smell, no more copy and paste. Binary search has two choices, one is to get rid of first half, or get rid of second half. Two recursive calls.

Here is the C# code, the code has the issue. If the first half is not in ascending order range, then one of boundary checked is ok then it is ok.

The above code passed all test cases in mock interview test cases, but it failed on Leetcode 33 online judge. The test case failed is [1, 3], 3.