Binary search is always my favorite

Nov. 23, 2017

Introduction

Binary search algorithm is my most favorite algorithm. I like to write it as a depth first search, recursive solution, and learn to write base case as the first thing in the function.

Code review 

Here is the C# code I wrote tonight. The mock interview started from 10:00 PM.

But the code smells, do not repeat yourself. DRY principle is violated.

The above code could not pass Leetcode 33 online judge, failed test case: [3, 1], 3, since the left half range can only include one node, so the fix is to include = sign in statement line 35.

Instead of "var firstHalfAscending = startValue < middleValue", it should be "var firstHalfAscending = startValue <= middleValue".

Follow up

Nov. 23, 2017

After the mock interview, I thought about my solutions in past practices. I should find a more simple solution.

In mock interview, peer asked me to explain the idea again to divide into two half range, one is in ascending order. I failed to make the idea very clear to a veteran programmer working over 10 years in Microsoft.

In other words, my code smells. Because I used the copy and paste in the mock interview, there are four recursive calls instead of traditional two recursive calls for binary search algorithm.

Based on the mock interview standard answer, it is to find pivot point first, and then apply binary search algorithm. Instead I applied binary search algorithm directly without concerning the pivot value.

Why? How did I make the different choices?

Of course, I spent hours to read all kind of solution on discussion panel of leetcode 33: Search in sorted rotated array before. I knew that there are almost millions of submissions, so many ideas. But bottom of my heart, I like to say that I went through mathematical training of analysis, I like to introduce two lemmas before I write code.

Lemma 1

The sorted array with length bigger than one is rotated to left with unknown n numbers, given the number n, n can be determined in the first half by the following checking:

Based on the fact that the first half range's length is not smaller than one.

How to determine if n can be searched in the first half range?

If the range is in ascending order, in other words, array[start] <= array[middle], and if n is in the range of [array[start], array[middle]], then n will be in the second half. Get rid of second half.

If the first half range is not in ascending order, then at least there are two elements in the first half range. It can be inferred that second half range is [array[middle], array[start] - 1]. The search number n is not in the second half range. Either the search number n is not smaller than array[start] or n is smaller than array[middle].

End of Lemma 1

One good solution with example

The C# code is here:

Here is the example to explain one inclusive range or two exclusive range to search:

More detail, exclude the range [4, 8] which is in ascending order in the above picture, two ranges are checked, one is >= 9 and the another one is < 3.

Nov. 24, 2017

Continue to update the code, use more meaningful variable names. C# Code is here.

How do I get here?

I have to get organized, so I went through blogs and reviewed all past practice on this algorithm, and also checked leetcode 33 submission history. I did not submit anything on Leetcode 33 before Nov. 22, 2017.

Past experience is documented here.

Sept. 16, 2017

The mock interview practice is documented here.


March 23, 2016

The practice is documented here.

Nov. 23, 2017

Leetcode 33, Search in Sorted Rotated array, C# code passes online judge.