求解 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.
*/
结果显示：Status: Runtime Error，Last executed input:[1], 0。 不知哪里错了 求大神解救！
我的程序：
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
                int first,last;
                vector<int> result;
                while(nums[first]!=nums[last])
                {
                        const int mid=first+0.5*(last-first);
                        if (nums[first] <= nums[mid]) {
                                if (nums[first] <= target && target < nums[mid])
                                        last = mid;
                                else
                                        first = mid + 1;
                                }
                        else
                        {
                                if (nums[mid] < target && target <= nums[last-1])
                                        first = mid + 1;
                                else
                                last = mid;
                        }

                }
       return -1;
    }
};

first和last都需要初始化。另外你的那个result数组是拿来干什么的？

mid 不是一直变吗，为什么前面加 const

你正确结果在哪儿return的。。。

不知道lz这样看明白了没有


class Solution {
public:
    int search(vector<int>& nums, int target) {
        int first=0,last=nums.size()-1;
        while(first <= last){
            int mid=first+(last-first)/2;
            if(nums[mid] == target) return mid;
            if (nums[first] <= nums[mid]) {
                if (nums[first] <= target && target < nums[mid])
                    last = mid-1;
                else
                    first = mid + 1;
            }else {
                if (nums[mid] < target && target <= nums[last])
                    first = mid + 1;
                else
                    last = mid-1;
            }
        }
       return -1;
        
    }
};

Java 版AC过的供楼主参考：

1. public class Solution {
   
2.     /**
   
3.      *@param A : an integer rotated sorted array
   
4.      *@param target :  an integer to be searched
   
5.      *return : an integer
   
6.      */
   
7.     public int search(int[] A, int target) {
   
8.         // write your code here
   
9.         int l = 0;
   
10.         int r = A.length - 1;
    
11.         
    
12.         for(int i = 0; i < A.length; i++)
    
13.         {
    
14.             int mid = (l+r) / 2;
    
15.             if(A[mid] == target)
    
16.             {
    
17.                 return mid;
    
18.             }
    
19.             else if(A[mid] < A[r])
    
20.             {
    
21.                 if(target > A[mid] && target <= A[r])
    
22.                 {
    
23.                     l = mid + 1;
    
24.                 }
    
25.                 else
    
26.                 {
    
27.                     r = mid - 1;
    
28.                 }
    
29.                
    
30.             }
    
31.             else
    
32.             {
    
33.                 if(target < A[mid] && target >= A[l])
    
34.                 {
    
35.                     r = mid - 1;
    
36.                 }
    
37.                 else
    
38.                 {
    
39.                     l = mid + 1;
    
40.                 }
    
41.             }
    
42.         }
    
43.         return -1;
    
44.     }
    
45. }
    

复制代码

用first<=last来控制循环会好写一点，另外循环里面没有return啊？

推荐 用first < last－1 作为循环条件

对于binary search类的题目，建议使用left + 1 < right作为循环条件，之后再判断left和right上的value。推荐模板：
http://www.shuatiblog.com/blog/2014/06/08/NineChap-Binary-Search/

同意楼上，亲测好用