(每日算法)LeetCode --- Search in Rotated Sorted Array(旋转数组的二分检索)

Search in Rotated Sorted Array I && II

Leetcode


对有序数组进行二分查找(下面仅以非递减数组为例):

  1. int binarySort(int A[], int lo, int hi, int target)
  2. {
  3. while(lo <= hi)
  4. {
  5. int mid = lo + (hi - lo)/2;
  6. if(A[mid] == target)
  7. return mid;
  8. if(A[mid] < target)
  9. lo = mid + 1;
  10. else
  11. hi = mid - 1;
  12. }
  13. }

对有序的旋转数组进行二分查找:

eg. [7, 8, 9, 3, 4, 5, 6]

在数组中有且仅有一个 断点 (数字由大变小)。

还是通过折半来实现,关键是如有巧妙的绕过这个断点。

1.如果前半部分有序:

  • target 在该区间内,则 hi = mid - 1
  • 不在该区间内,则 lo = mid + 1

2.如果前半部分无序

  • target 在后半部分的有序区间内,则 lo = mid + 1
  • 不在该区间内, 则 hi = mid - 1

也就是说,我们优先考虑有序的部分。

  1. int search(int A[], int lo, int hi, int target)
  2. {
  3. while (lo <= hi)
  4. {
  5. int mid = (lo + hi) / 2;
  6. if (A[mid] == target)
  7. return mid;
  8. if (A[lo] <= A[mid])
  9. {
  10. if (A[lo] <= target && target < A[mid])
  11. hi = mid - 1;
  12. else
  13. lo = mid + 1;
  14. } else {
  15. if (A[mid] < target && target <= A[hi-1])
  16. lo = mid + 1;
  17. else
  18. hi = mid - 1;
  19. }
  20. }
  21. return -1;
  22. }

对包含重复元素的旋转数组进行二分查找:

允许重复元素,则上一题中如果A[m]>=A[l],那么[l,m]为递增序列的假设就不能成立了,比如[1,3,1,1,1]。

如果A[m]>=A[l]不能确定递增,那就把它拆分成两个条件:

  • 若A[m]>A[l],则区间[l,m]一定递增
  • 若A[m]==A[l]确定不了,那就l++,往下看一步即可。
  1. bool search(int A[], int lo, int hi, int target)
  2. {
  3. while (lo <= hi)
  4. {
  5. int mid = (lo + hi) / 2;
  6. if (A[mid] == target)
  7. return true;
  8. if (A[lo] < A[mid])
  9. {
  10. if (A[lo] <= target && target < A[mid])
  11. hi = mid - 1;
  12. else
  13. lo = mid + 1;
  14. } else if(A[lo] > A[mid]) {
  15. if (A[mid] < target && target <= A[hi-1])
  16. lo = mid + 1;
  17. else
  18. hi = mid - 1;
  19. }
  20. else
  21. lo++;
  22. }
  23. return false;
  24. }
时间: 12-09

(每日算法)LeetCode --- Search in Rotated Sorted Array(旋转数组的二分检索)的相关文章

LeetCode: Search in Rotated Sorted Array

LeetCode: Search in Rotated Sorted Array 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. If found in the array return its index, othe

Leetcode | Search in Rotated Sorted Array I &amp; II

Search in Rotated Sorted Array I 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. If found in the array return its index, otherwise re

LeetCode: Search in Rotated Sorted Array II 解题报告

Search in Rotated Sorted Array II Follow up for "LeetCode: Search in Rotated Sorted Array 解题报告":What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the arr

[LeetCode] Search in Rotated Sorted Array [35]

题目 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. If found in the array return its index, otherwise return -1. You may assume no dup

[leetcode]Search in Rotated Sorted Array @ Python

原题地址:https://oj.leetcode.com/problems/search-in-rotated-sorted-array/ 题意: 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. If found in

[leetcode]Search in Rotated Sorted Array II @ Python

原题地址:https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/ 题意: 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 to determine if

[LeetCode] Search in Rotated Sorted Array II [36]

题目 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 to determine if a given target is in the array. 原题链接(点我) 解题思路 这题和Search in Rotated Sorted

LeetCode: Search in Rotated Sorted Array 解题报告

Search in Rotated Sorted Array 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. If found in the array return its index, otherwise retu

[LeetCode] Search in Rotated Sorted Array I (33) &amp;&amp; II (81) 解题思路

33. Search in Rotated Sorted Array 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. If found in the array return its index, otherwise