1 #include "000库函数.h"  2   3 //自解  68ms  弱爆了  4 //先找到最大值，然后确定目标值在最大值的左边还是右边  5 //最后使用折中寻找法，找到目标值的位置,此方法应该满足复杂度不超过logn的要求  6 class Solution {  7 public:  8     int search(vector
     
      & nums, int target) {  9         if (nums.size() == 0)return -1; 10  11         int maxValue = *max_element(nums.begin(), nums.end());//最大值 12         int maxPosition = max_element(nums.begin(), nums.end()) - nums.begin();//最大值的位置  13         if (target > maxValue)return -1; 14         if (target == maxValue)return maxPosition; 15         int i, j, t; 16         if (target >= nums[0]) { 17             i = 0; 18             j = maxPosition; 19         } 20         else { 21             i = maxPosition+1; 22             j = nums.size() - 1; 23         }         24         while (i <= j) { 25             t = (i + j) / 2; 26             if (target == nums[t]) 27                 return t; 28             else if (target > nums[t]) 29                 i = t + 1; 30             else 31                 j = t - 1; 32         } 33         return -1; 34     } 35 }; 36  37 //这道题的关键在与，找到哪一部分是升序的 38 //旋转数组有个特点，中间数的左右两边有一边一定是升序的，另一边就不一定了 39 //此种解法满足复杂度logn的要求  20ms 40 /* 41  42 0　　1　　2　　 4　　5　　6　　7 43  44 7　　0　　1　　 2　　4　　5　　6 45  46 6　　7　　0　　 1　　2　　4　　5 47  48 5　　6　　7　　 0　　1　　2　　4 49  50 4　　5　　6　　7　　0　　1　　2 51  52 2　　4　　5　　6　　7　　0　　1 53  54 1　　2　　4　　5　　6　　7　　0 55  56  57 */ 58 class Solution { 59 public: 60     int search(vector
      
       & nums, int target) { 61         if (nums.size() == 0)return -1; 62         int i = 0, j = nums.size() - 1; 63         while (i <= j) { 64             int t = i + (j - i) / 2;//找到此时序列的中间位置 65             if (target == nums[t])return t; 66             if (nums[t] < nums[j]) {    //此时右边为升序 67                 if (nums[t] < target&&target <= nums[j])//目标函数位于右边 68                     i = t + 1; 69                 else 70                     j = t - 1; 71             } 72             else { 73                 if (nums[i] < target && nums[t]>target) 74                     j = t - 1; 75                 else 76                     i = t + 1; 77             } 78         } 79         return -1; 80     } 81 }; 82  83  84 class Solution { 85 public: 86     int search(vector
       
        & nums, int target) { 87         if (nums.size() == 0)return -1; 88         for (int i = 0; i < nums.size(); ++i) { 89             if (target == nums[i]) 90                 return i; 91         } 92         return -1; 93  94  95  96     } 97 }; 98  99 void T033() {100     Solution s;101     vector
        
         n;102     n = { 3,1 };103     cout << s.search(n, 1) << endl;104     n = { 4,5,6,7,0,1,2 };105     cout << s.search(n, 4) << endl;106     n = { 4,5,6,7,0,1,2 };107     cout << s.search(n, 7) << endl;108     n = { 4,5,6,7,0,1,2 };109     cout << s.search(n, 2) << endl;110     n = { 4,5,6,7,0,1,2 };111     cout << s.search(n, 0) << endl;112 113 }