Search in a rotated sorted array II@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

» Solve this problem

本题的思路核心仍然是search in a rotated sorted array没有duplicate版，它的思想是把可能的情况考虑到并且分类。现在有duplicate，会增加什么情况呢？无非就是比较的时候A[L]==A[M]的情况，而这种情况是可以包括在之前讨论的情况里的，只是需要一些小的处理，就是加了一行
while(A[M]==A[L]&&L<M) M++; (M--;)
这样就可以把相等的元素给跳过，直到不相等的，这样再做binary search就相当于没有duplicate一样。同时，还有一个细节，就是在判断相等的时候要不要包括等于号，这个很关键，因为它很可能会漏掉一些元素，这个在自己脑海里跑程序的时候会注意到。

可以对比我的此题的两个版本。i 和 ii。