LeetCode之Search in Rotated Sorted Array

【题目】

Search in Rotated Sorted Array

Suppose a sorted array 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.

【分析】

使用二分查找，若中间数大于等于最左端数，那左半部分必定有序，否则右半部分有序，通过将目标数与有序部分的最大与最小数比较就可以判断目标数位于哪一部分

【代码】

/*********************************
*   日期：2014-01-15
*   作者：SJF0115
*   题号: Search in Rotated Sorted Array
*   来源：http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     using namespace std; class Solution { public: //二分查找 int search(int A[], int n, int target) { int start = 0,end = n-1; int mid; while(start <= end){ mid = (start + end) / 2; if(A[mid] == target){ return mid; } //中间元素大于最左边元素则左部分为有序数组 else if(A[mid] >= A[start]){ //目标位于左部分 if(target >= A[start] && target <= A[mid]){ end = mid - 1; } //目标位于右部分 else{ start = mid + 1; } } //中间元素小于最右边元素则右部分为有序数组 else{ //目标位于左部分 if(target <= A[end] && target >= A[mid]){ start = mid + 1; } //目标位于左部分 else{ end = mid - 1; } } } return -1; } }; int main() { int result; Solution solution; int A[] = {3,1}; result = solution.search(A,2,1); printf("Result:%d\n",result); return 0; }