33. 搜索旋转排序数组

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

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

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

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

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

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0

输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3

输出: -1

class Solution {

public:

    int search(vector<int>& nums, int target) {

        int l = 0;

        int r = nums.size() - 1;

        while(l <= r)

        {

            int mid = (l + r)/2;

            if(target == nums[mid])

                return mid;

            else if(target < nums[mid])

            {

                if(nums[l] < nums[mid])

                {

                    if(target >= nums[l])

                        r = mid - 1;

                    else 

                        l = mid + 1;

                }

                else if(nums[l] > nums[mid])

                    r = mid - 1;

                else if(nums[l] == nums[mid])

                    l = mid + 1;

            }

            else if(target > nums[mid])

            {

                if(nums[l] < nums[mid])

                    l = mid + 1;

                else if(nums[l] > nums[mid])

                {

                    if(target >= nums[l])

                        r = mid - 1;

                    else    

                        l = mid + 1;

                }

                else if(nums[l] == nums[mid])

                    l = mid + 1;

            }

        }

        return -1;

    }

};

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容