旋转数组找一个数

2019/03/14 22:15
阅读数 9

 

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

思路:二分,二分之后的某一段必然是有序的。另一段必然是是部分有序的。如果落在有序的一段,直接二分找出该值。

         如果是落在另一段部分有序的,继续二分,该部分是递归的,有一段是有序的,另一段是部分有序的。

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////l

from StefanPochmann https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14419/Pretty-short-C%2B%2BJavaRubyPython

用异或来判断三段的升降序。

int search(vector<int>& nums, int target) {
    int lo = 0, hi = int(nums.size()) - 1; while (lo < hi) { int mid = (lo + hi) / 2; if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) lo = mid + 1; else hi = mid; } return lo == hi && nums[lo] == target ? lo : -1; }
展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部