Leetcode 33: Search in Rotated Sorted Array

Sept. 16, 2017

Introduction

It is the wonderful learning opportunity for me to practice the algorithm again last night at 10:00 pm. I chose to write the idea I thought about and read about, but I had not written it before. The experience told me that binary search basically is also like a depth first search, the most important is to work on base case.

The more detail is like this, I spent first 15 minutes to exchange ideas with the peer, and then only 13 minutes left, I need to write some code, and I chose to write a binary search combining normal binary search in sorted array and shift array binary search. My argument is that the normal one is just special case of shifted array binary search. The iterative solution is hard to avoid duplicate logic and coding. I just could not believe that I made it the first writing without any bug or grammar error.


Leetcode 33 is a medium algorithm, I wrote down the algorithm in less than 13 minutes, and most important thing I did is to move base case "middle value" (line 29 - 32) to the first thing inside the while loop, moved those 4 lines out of if block from line 36 to 46.

Tip to share 

I got the complaint about my practice of binary search tree. The peer told me that the most important part is to work on middle value in the binary search tree. Focus on middle value, do not consider start value at all.

Algorithm practice 

C# code practice is here.