面试金典--11.3

题目描述：给定一个数组，数组是由一个排好序的数组循环旋转得到的，现在要在数组中找给定值

思路：

(1)递归，二分查找，左右子数组肯定会有一个是排好序的，比较a[mid]与a[l]的大小之后，判断哪部分排好序，然后判断目标值在哪部分

特殊情况是：2 2 2 3 2 2 2 2这种情况，中间元素与左边元素相同，如果中间与右边元素相同也就是给的这种情况，就得查找左右两部分；

如果不相同，那么直接查找右边部分就行

（2）迭代，上述的特殊情况不好实现；有知道的欢迎指教

  1 #include <iostream>
  2 #include <queue>
  3 #include <climits>
  4 #include <algorithm>
  5 #include <memory.h>
  6 #include <stdio.h>
  7 using namespace std;
  8 
  9 int fun(vector<int> a,int target)
 10 {
 11     int l = 0;
 12     int r = a.size()-1;
 13     while(l <= r)
 14     {
 15         int mid = (l+r)/2;
 16         if(a[mid] == target)
 17             return mid;
 18         if(a[l] < a[mid])
 19         {
 20             if(a[l] <= target && a[mid] > target)
 21             {
 22                 r = mid-1;
 23             }
 24             else
 25             {
 26                 l = mid+1;
 27             }
 28         }
 29         else if(a[l] > a[mid])
 30         {
 31             if(a[r] >= target && a[mid] < target)
 32             {
 33                 l = mid+1;
 34             }
 35             else
 36             {
 37                 r = mid-1;
 38             }
 39         }
 40         else
 41         {
 42             //这块不好写成非递归了
 43         }
 44     }
 45     return -1;
 46 }
 47 //递归算法
 48 int fun_2(vector<int> a,int target,int l,int r)
 49 {
 50     int mid = (l+r)/2;
 51     if(a[mid] == target)
 52         return mid;
 53     if(l > r)
 54         return -1;
 55     if(a[l] < a[mid])
 56     {
 57         if(a[l] <= target && a[mid] > target)
 58         {
 59             return fun_2(a,target,l,mid-1);
 60         }
 61         else
 62         {
 63             return fun_2(a,target,mid+1,r);
 64         }
 65     }
 66     else if(a[l] > a[mid])
 67     {
 68         if(a[mid] < target && a[r] >= target)
 69         {
 70             return fun_2(a,target,mid+1,r);
 71         }
 72         else
 73         {
 74             return fun_2(a,target,l,mid-1);
 75         }
 76     }
 77     else
 78     {
 79         if(a[mid] != a[r])
 80         {
 81             return fun_2(a,target,mid+1,r);
 82         }
 83         else
 84         {
 85             int res = fun_2(a,target,l,mid-1);
 86             if(res == -1)
 87             {
 88                 return fun_2(a,target,mid+1,r);
 89             }
 90             else
 91                 return res;
 92         }
 93     }
 94     return -1;
 95 }
 96 
 97 int main()
 98 {
 99     vector<int> a;
100     a.push_back(15);
101     a.push_back(16);
102     a.push_back(19);
103     a.push_back(20);
104     a.push_back(25);
105     a.push_back(1);
106     a.push_back(3);
107     a.push_back(4);
108     a.push_back(5);
109     a.push_back(7);
110     a.push_back(10);
111     a.push_back(14);
112 
113     cout<<fun_2(a,5,0,11);
114     return 0;
115 }