LeetCode - 33. Search in Rotated Sorted Array

本文主要是介绍LeetCode - 33. Search in Rotated Sorted Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

33. Search in Rotated Sorted Array

Problem's Link

----------------------------------------------------------------------------

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; 
 } 
 /* 
 
 */ 