LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

33.Search in Rotated Sorted Array

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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

题目大意:对于一个旋转后的有序数组经查找操作,注意算法的时间复杂度要求是O(logn)。

思路:对于O(logn)复杂度和有序数组,我们很容易想到采用二分搜索法,但是这个有序的数组经过旋转了,那么我们是否有方法让这个旋转后的数组变为严格意义上的有序数组呢?可以,但是想来想去,这种操作的复杂度会高于O(logn)。因此这种方法行不通。但是我们发现,数组是有两段的,这两段中必定有一段是严格意义上递增的数组,因此,我们就可以这这一段有序的数组上进行二分查找法。

 Share my intuitive thinking: the main idea is that we need to find some parts of array
 that we could adopt binary search on that, which means we need to find some completed 
 sorted parts, then determine whether target is in left part or right part. There is at 
 least one segment (left part or right part) is monotonically increasing.

解法:

    public int search(int[] nums, int target) {
        if (nums == null || nums.length ==0) return -1;
        int left = 0 ,right = nums.length-1,mid;
        while (left<=right){
            mid = left+(right-left)/2;
            if (nums[mid] == target ) return mid;
            if (nums[left] <= nums[mid]){
                //left to mid is monotonically increasing
                if (target < nums[mid] && target>=nums[left]){
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else {
                //mid to right is monotonically increasing
                if (target<=nums[right]&& target>nums[mid]){
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }
        }
        return  -1;
    }

81.Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

题目大意:对于一个旋转后的有序数组经查找操作,注意这里的数组是有重复数字的。

思路:对于没有重复数字的旋转数组,我们很好的解决了将其转化为严格有序数组的问题,但是这个有重复数字的旋转的数组与上一题有什么区别呢?我们发现,当同样采用上面的思路的时候会存在一种情况:无法根据(nums[left]<= nums[mid])这一句来判断那一段严格的递增了,因为会存在首位是同一个数字的情况,例如: [2,5,6,0,0,1,2];所以,我们要对这种特殊的情况进行处理,也就是让此时的left和right所指向的数字是不同的,因此我们加入以下的处理:

while(left < right && nums[left]== nums[right]) left++;

这样可以很好的解决上的问题。

解法:

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

总结:二分搜索有较多的变形,参照《LeetCode 34.Find First and Last Position of Element in Sorted Array》

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

java 之容器

在Java中,我们想要保存对象可以使用很多种手段。我们之前了解过的数组就是其中之一。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们...

2468
来自专栏编程

Python变量与数据类型

1 Python中数据类型 1、整数 Python可以处理任意大小的整数,当然包括负整数,在Python程序中,整数的表示方法和数学上的写法一模一样,例如:,,...

2806
来自专栏BestSDK

封装、私有,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

3693
来自专栏数据结构与算法

1245 最小的N个和

1245 最小的N个和 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...

2745
来自专栏Kevin-ZhangCG

[ Java面试题 ] 集合篇

2037
来自专栏彭湖湾的编程世界

【Java】泛型学习笔记

我的博客即将入驻“云栖社区”,诚邀技术同仁一同入驻。 参考书籍 《Java核心技术:卷1》 泛型, 先睹为快 先通过一个简单的例子说明下Java中泛型的用法: ...

3878
来自专栏转载gongluck的CSDN博客

python笔记:#008#变量的命名

变量的命名 目标 标识符和关键字 变量的命名规则 0.1 标识符和关键字 1.1 标识符 标示符就是程序员定义的 变量名、函数名 名字 需要有 见名知义 的...

3714
来自专栏成猿之路

Java面试题-基础篇一

1123
来自专栏浪淘沙

Scala学习笔记

大数据框架(处理海量数据/处理实时流式数据) 一:以hadoop2.X为体系的海量数据处理框架         离线数据分析,往往分析的是N+1的数据  ...

3984
来自专栏文武兼修ing——机器学习与IC设计

表的应用——排序与描述多项式排序多项式ADTGO语言笔记

排序 朴素排序 在链表建立的过程中可以直接完成排序功能,即建立一个新链表并将源数据一个一个存进新链表中,每个元素存储的位置在小于这个元素的节点和大于这个元素的节...

3486

扫码关注云+社区

领取腾讯云代金券