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.

思路：此题在解的时候，才发现Search in Rotated Sorted Array的时候想复杂了，事实上仅仅须要遍历搜索就可以，线性时间。

代码例如以下：

public class Solution {    public boolean search(int[] nums, int target) {        for(int i = 0; i < nums.length; i++){            if(nums[i] == target){                return true;            }        }        return false;    }}