C++实现LeetCode(33.在旋转有序数组中搜索)

[LeetCode] 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

这道题让在旋转数组中搜索一个给定值，若存在返回坐标，若不存在返回 -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 {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 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;
    }
};

看了上面的解法，你可能会产生个疑问，为啥非得用中间的数字跟最右边的比较呢？难道跟最左边的数字比较不行吗，当中间的数字大于最左边的数字时，左半段也是有序的啊，如下所示（蓝色表示中点之前一定为有序的）：

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

貌似也可以做，但是有一个问题，那就是在二分搜索中，nums[mid] 和 nums[left] 还有可能相等的，当数组中只有两个数字的时候，比如 [3, 1]，那该去取那一边呢？由于只有两个数字且 nums[mid] 不等于 target，target 只有可能在右半边出现。最好的方法就是让其无法进入左半段，就需要左半段是有序的，而且由于一定无法同时满足 nums[left] <= target && nums[mid] > target，因为 nums[left] 和 nums[mid] 相等，同一个数怎么可能同时大于等于 target，又小于 target。由于这个条件不满足，则直接进入右半段继续搜索即可，所以等于的情况要加到 nums[mid] > nums[left] 的情况中，变成大于等于，参见代码如下：

解法二：

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

讨论：这道题的二分搜索的解法实际上是之前的总结帖 LeetCode Binary Search Summary 二分搜索法小结 中的第五类，也是必须要将 right 初始化为 nums.size()-1，且循环条件必须为小于等于。二分搜索法真是博大精深，变化莫测啊～

到此这篇关于C++实现LeetCode(33.在旋转有序数组中搜索)的文章就介绍到这了,更多相关C++实现在旋转有序数组中搜索内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-

  • C++实现LeetCode(28.实现strStr()函数)

    [LeetCode] 28. Implement strStr() 实现strStr()函数 Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 E

  • C++实现LeetCode(27.移除元素)

    [LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with

  • C++实现LeetCode(29.两数相除)

    [LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

  • C++实现LeetCode(30.串联所有单词的子串)

    [LeetCode] 30. Substring with Concatenation of All Words 串联所有单词的子串 You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words ex

  • C++实现LeetCode(31.下一个排列)

    [LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 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 f

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 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.

  • C++实现LeetCode(153.寻找旋转有序数组的最小值)

    [LeetCode] 153. Find Minimum 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]). Find the minimum element. You may

  • C++实现LeetCode(154.寻找旋转有序数组的最小值之二)

    [LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二 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]). Find the minimum element. Th

  • C++实现LeetCode(88.混合插入有序数组)

    [LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has

  • C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

    [LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

  • java算法入门之有效的括号删除有序数组中的重复项实现strStr

    java算法入门之有效的括号删除有序数组中的重复项实现strStr

    目录 1.LeetCode 20.有效的括号 题目 小编菜解 思路及算法 大神解法 2.LeetCode 26.删除有序数组中的重复项 题目 小编菜解初版 小编菜解改进版 思路及算法 大神解法 3.LeetCode 28.实现strStr 题目 小编菜解 大神解法 也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1

  • java实现向有序数组中插入一个元素实例

    整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha

随机推荐