Monday, July 18, 2016

Leetcode 81 - Search in Rotated Sorted Array II

http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-ii-java/
Follow up for "Search in Rotated Sorted Array": what if duplicates are allowed? Write a function to determine if a given target is in the array.
```public boolean search(int[] nums, int target) {
int left=0;
int right=nums.length-1;

while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target)
return true;

if(nums[left]<nums[mid]){
if(nums[left]<=target&& target<nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}else if(nums[left]>nums[mid]){
if(nums[mid]<target&&target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}else{
left++;
}
}

return false;
}```

http://www.cnblogs.com/anne-vista/p/4899753.html

3 1 2 3 3 3 3
3 3 3 3 1 2 3

A[mid] = A[end] != target时：搜寻A[start : end-1]

```    public boolean search(int[] nums, int target) {
int left = 0, right = nums.length-1;
int index = -1;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target) {
index = mid;
}
if(nums[mid] < nums[right]) { //right half sorted
if(target > nums[mid] && target <= nums[right]){
left = mid+1;
}else{
right = mid-1;
}
}else if(nums[mid] > nums[right]){ //left half sorted
if(target >= nums[left] && target < nums[mid]){
right = mid-1;
}else {
left = mid+1;
}
}else{
right--;
}
}
return index != -1;
}```

http://codesniper.blogspot.com/2015/03/81-search-in-rotated-sorted-array-ii.html