33. Search in Rotated Sorted Array
----------------------------------------------------------------------------
Mean:
给你一个数组，这个数组是由两个有序的数组拼接成的（无重复元素），在这个数组中查找元素k的下标.
analyse:
既然是由两个有序数组拼接而成，那么只需找到断点，然后进行两次二分查找就行.
Time complexity: O(N)
view code
/** * ----------------------------------------------------------------- * Copyright (c) 2016 crazyacking.All rights reserved. * ----------------------------------------------------------------- * Author: crazyacking * Date : 2016-03-01-21.22 */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long( LL); typedef unsigned long long( ULL); const double eps( 1e-8); class Solution { public : int search( vector < int >& nums , int target) { int len = nums . size(); int low1 = 0 , high1 = len - 1 , low2 = 0 , high2 = len - 1; for( int i = 1; i < len; ++ i) { if( nums [ i ] < nums [ i - 1 ]) { high1 = i - 1 , low2 = i; break; } } if( high1 == len - 1 && low2 == 0) return isExist( nums , low1 , high2 , target); else { int idx1 = isExist( nums , low1 , high1 , target); int idx2 = isExist( nums , low2 , high2 , target); if( idx1 ==- 1 && idx2 ==- 1) return - 1; else return idx1 !=- 1 ? idx1: idx2; } } int isExist( vector < int >& nums , int low , int high , int target) { while( low <= high) { int mid =( low + high) >> 1; if( target < nums [ mid ]) high = mid - 1; else if( target > nums [ mid ]) low = mid + 1; else return mid; } return - 1; } }; int main() { Solution solution; int n , k; vector < int > ve; while( cin >>n >> k) { int tempVal; for( int i = 0; i <n; ++ i) { cin >> tempVal; ve . push_back( tempVal); } int ans = solution . search( ve , k); cout << ans << endl; } return 0; } /* */