# Search-in-Rotated-Sorted-Array

Oct 09, 2017

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

if (nums[first] > nums[last]) {
while(last >= 0 && nums[first] > nums[last] && nums[last] < target)
last--;
while(first <= last &&  nums[first] > nums[last] && nums[first] > target)
first++;
}
//binarySearch


if(nums[first] > nums[last]) {
int f= first,l = last;
//找转折点
while(f <= l) {
mid = (f + l)/2;
if (nums[mid] > nums[mid + 1]) break;
else if (nums[mid] > nums[first]) f = mid + 1;
else if (nums[mid] < nums[last]) l = mid;
}
if (target > nums[last]) last = mid;
else if (target < nums[first]) first = mid + 1;
else if (target == nums[first]) return first;
else return last;
}
//binary Serarch


int search(vector<int>& nums, int target) {
int first = 0,last = nums.size() - 1;
int mid;

if (last < 0) return -1;

if(nums[first] > nums[last]) {
int f= first,l = last;
//找转折点
while(f <= l) {
mid = (f + l)/2;
if (nums[mid] > nums[mid + 1]) break;
else if (nums[mid] > nums[first]) f = mid + 1;
else if (nums[mid] < nums[last]) l = mid;
}
if (target > nums[last]) last = mid;
else if (target < nums[first]) first = mid + 1;
else if (target == nums[first]) return first;
else return last;
}
cout << first << last;
//binary search
while(first <= last) {
int mid = (first + last)/2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) first = mid + 1;
else last = mid - 1;
}
return -1;
}


public int search(int[] A, int target) {
int lo = 0;
int hi = A.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (A[mid] == target) return mid;

if (A[lo] <= A[mid]) {
if (target >= A[lo] && target < A[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if (target > A[mid] && target <= A[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return A[lo] == target ? lo : -1;
}

LeetCodeLeetCodeSearch

Next-Permutation

Generate Parentheses