O(N)
if element can repeat, the worst case, you cannot throw away any section. eg. [1, 1, 1, 1, 0, 1, 1] target = 0, you cannot throw any section. We have to loop through to check.
public class Solution { /** * param A : an integer ratated sorted array and duplicates are allowed * param target : an integer to be search * return : a boolean */ public boolean search(int[] A, int target) { // write your code here if (A == null || A.length == 0) { return false; } for (int i = 0; i < A.length; i++) { if (A[i] == target) { return true; } } return false; } }
Search in Rotated Sorted Array II
原文：http://www.cnblogs.com/codingEskimo/p/6805076.html