频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
Leetcode 33 Search in Rotated Sorted Array 二分查找变式
2016-09-06 09:26:08         来源:无名山丘,崛起成峰  
收藏   我要投稿

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 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.

在循环错位的有序数组中找出特定元素。

二分的一个变式,分情况讨论一下,详见注释。

 

class Solution {
public:
    int search(vector& nums, int target) 
    {
        int l=0,r=nums.size()-1;
        while(l<=r)
        {
            int mid=(r+l)/2;
            if(nums[mid]==target) 
                return mid;
            if(nums[mid]>=nums[l]) //mid在左侧大一些的区间
            {
                if(nums[l]<=target && nums[mid]>target) //target比mid小,但大于l,向左移
                    r=mid-1;
                else
                    l=mid+1;
            }
            else //mid在右侧小一些的区间
            {
                if(nums[r]>=target && nums[mid]

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 二分查找变式
上一篇:zigbee学习重点资料的摘录1
下一篇:CAS实现单点登录SSO执行原理探究
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站