一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 443|回复: 8
收起左侧

[算法题] 求解 Search in Rotated Sorted Array

[复制链接] |试试Instant~ |关注本帖
回帖奖励 2 根萝卜 回复本帖可获得 1 根萝卜奖励! 每人限 1 次(中奖概率 80%)
lcx813 发表于 2015-6-2 11:09:16 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目:/*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;
    }
};




stellari 发表于 2015-6-2 14:23:10 | 显示全部楼层

回帖奖励 +1 根萝卜

first和last都需要初始化。另外你的那个result数组是拿来干什么的?
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-6-8 02:38:46 | 显示全部楼层

回帖奖励 +1 根萝卜

mid 不是一直变吗,为什么前面加 const
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-6-8 03:19:14 | 显示全部楼层

回帖奖励 +1 根萝卜

你正确结果在哪儿return的。。。
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-6-8 21:06:22 | 显示全部楼层

回帖奖励 +1 根萝卜

不知道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;
        
    }
};
回复 支持 反对

使用道具 举报

love1point 发表于 2015-6-9 10:41:10 | 显示全部楼层

回帖奖励 +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. }
复制代码
回复 支持 反对

使用道具 举报

liuzonyuan 发表于 2015-6-10 09:24:29 | 显示全部楼层

回帖奖励 +1 根萝卜

用first<=last来控制循环会好写一点,另外循环里面没有return啊?
回复 支持 反对

使用道具 举报

yuwang1986s 发表于 2015-6-11 16:33:48 | 显示全部楼层

回帖奖励 +1 根萝卜

推荐 用first < last-1 作为循环条件
回复 支持 反对

使用道具 举报

iker01 发表于 2015-6-12 00:38:56 | 显示全部楼层

回帖奖励 +1 根萝卜

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 13:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表