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.

解题思路

这道题目我是参考这位大神的博客链接地址。 我简单说一说他的思路，这道题目我们使用的基本方法是二分法，因为二分法查找的效率比较高，具体和二分法有一点不同，二分法是判断nums[mid] 和 target的关系（数组中间值和被查找的数）。 这里我们是判断数组中nums[mid] 和 nums[right]的关系（数组中间值和最右边的值）。如果nums[mid] > nums[right]，那么数组旋转过的，而且小半部分在右边，然后用target针对nums[mid] 和 nums[left]进行深入判断，得出left或者right下次的定位。不断推进，找出那个值，如果没有则返回-1。

我的解答

// // main.cpp // leetcode33 // // Created by 李林 on 16/9/27. // Copyright © 2016年 lilin. All rights reserved. // #include <iostream> #include <vector> using namespace std; class Solution { public: // 《算法笔记》page127普通二分法 int search(vector<int>& nums, int target) { int size = nums.size(); int left = 0, right = size-1, mid; while(left <= right){ mid = (left+right) / 2; if(nums[mid] == target) return mid; // 和二分法的思维区别开来(分两种不同的模型) if(nums[mid] < nums[right]){ if(target>nums[mid] && target<=nums[right]) left = mid+1; else right = mid-1;; }else{ if(target>=nums[left] && target<nums[mid]) right = mid-1; else left = mid+1; } } return -1; } }; int main() { Solution s; vector<int> nums; int array[2] = {1, 3}; for(int i=0; i<2; i++) nums.push_back(array[i]); int result = s.search(nums, 3); printf("%d", result); return 0; }