文档章节

在翻转数组中查找给定值 Search in Rotated Sorted Array

叶枫啦啦
 叶枫啦啦
发布于 2017/09/02 16:07
字数 779
阅读 14
收藏 0

问题:

Suppose an array sorted in ascending order 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.

解决:

① http://www.cnblogs.com/grandyang/p/4325648.html

这道题让在旋转数组中搜索一个给定值,若存在返回坐标,若不存在返回- 1。使用二分搜索法,但是这道题的难点在于我们不知道原数组在哪旋转了,我们还是用题目中给的例子来分析,对于数组[0 1 2 4 5 6 7] 共有下列七种旋转方法:

0  1  2   4  5  6  7
7  0  1   2  4  5  6
6  7  0   1  2  4  5
5  6  7   0  1  2  4
4  5  6   7  0  1  2
2  4  5   6  7  0  1
1  2  4   5  6  7  0

二分搜索法的关键在于获得了中间数后,判断下面要搜索左半段还是右半段,我们观察上面红色的数字都是升序的,由此我们可以观察出规律,如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了

class Solution {//16ms
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if(nums[mid] < nums[right]){//右半段是递增的,一定要先判断右半段,考虑3,2,1这样的情况
                if(nums[mid] < target && nums[right] >= target) left = mid + 1;//目标在右半段
                else right = mid - 1;//在左半段
            }else{//左半段是递增的
                if(nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
}

② 括号还是挺重要的,可以提高效率。

class Solution {//14ms
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if(nums[mid] < nums[right]){//右半段是递增的
                if(nums[mid] < target && nums[right] >= target) {
                    left = mid + 1;//目标在右半段
                }else {
                    right = mid - 1;//在左半段
                }
            }else{//左半段是递增的
                if(nums[left] <= target && nums[mid] > target){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}

【注】输入为[3,2,1],3时,折半查找时结果错误会输出-1

③ 所以对判断条件进行了修改。

class Solution{
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] < nums[right]){
                if (mid + 1 < nums.length && nums[mid + 1] <= target && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }else{
                if (mid - 1 >= 0 && nums[left] <= target && target <= nums[mid - 1]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}

④ 直接扫描数组查找。

class Solution {//15ms
    public int search(int[] nums, int target) {     
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] == target)
                return i;
        }
        return -1;
    }
}

 

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
Lintcode39 Recover Rotated Sorted Array solution 题解

【题目描述】 Given a rotated sorted array, recover it to sorted array in-place. 给定一个旋转排序数组,在原地恢复其排序。 【题目链接】 http://www.lintcode.com/en/problem/recover...

abcdd1234567890
2018/06/29
0
0
搜索旋转的排序数组

原题   Follow up for “Search in Rotated Sorted Array”:   What if duplicates are allowed?   Would this affect the run-time complexity? How and why?   Write a function ......

一贱书生
2016/12/19
42
0
Lintcode62 Search in Rotated Sorted Array solution 题解

【题目描述】 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. I......

Winnielyn
2018/06/26
0
0
在旋转数组中搜索

原题   Suppose a sorted array is rotated at some pivot unknown to you beforehand.   (i.e., might become ).   You are given a target value to search. If found in the array......

一贱书生
2016/12/14
1
0
算法与数据结构(六):旋转有序数组搜索总结

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/Dbyfreedom/article/details/94331072 旋转有序数组搜索总结 LeetCo...

dby_freedom
06/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

秒杀系统思路

业务分析 技术挑战 请求响应要快:无论成功失败,需要尽快返回给用户 架构设计   前端:静态化   站点层:限制请求数   服务层:乐观锁写缓存   数据库CAP:读写高可用,一致性,扩容...

雷开你的门
16分钟前
7
0
最全的教育行业大数据解决方案,个个针对痛点

大数据的悄然兴起也带动了教育行业的革新,移动教育、云课堂等的出现,使得教育行业再次成为了可以中长期保持高景气的行业。然而,初涉数据领域的教育行业同时也面临着相当大的难题,还需要更...

朕想上头条
20分钟前
5
0
预约模块设计分析

1.预约功能描述: 预约是小程序中常见的一种商品管理系统,商家可根据商品或服务的特性,灵活设置预约细节,为用户提供线上预约服务,如场地预约,商品预定等,实现高效经营。 预约场景: ...

鱼煎
24分钟前
4
0
阿里云日志服务构建网站实时分析大盘实战

场景分析 挖掘数据价值是当前企业级网站共同面临的问题。买买网是一个电商平台网站,每天拥有大量的用户访问和购买记录。为了引导用户直接消费,提升购买率和转化率,不同的用户类别需要推荐...

阿里云官方博客
25分钟前
2
0
TL665xF-EasyEVM开发板硬件处理器、NAND FLASH、RAM

广州创龙结合TI KeyStone系列多核架构TMS320C665x及Xilinx Artix-7系列FPGA设计的TL665xF-EasyEVM开发板是一款DSP+FPGA高速大数据采集处理平台,其底板采用沉金无铅工艺的6层板设计,适用于高...

Tronlong创龙
28分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部