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 return -1.
You may assume no duplicate exists in the array.
我突然想用英文解说下,展示一下我英文解说这么专业主题的功力O(∩_∩)O~,都搞双语的话好像又太费时间了。
This is a classic interview question. It's solution is similar with normal binary search. The only difference is that we need to add more conditional sentences.
和普通的二分法差不多
The key points is when we divide the array into two half, we need to compare A[mid] with one of the end element of the array, so that we can know which half of the array is sorted, and which half is rotated, and divided them again subsequently.
关键是会增加条件判断
The difference I do here is that I add one normal binary search here as a helper function. Actually you don't need the binary search function, just one function will be alright. But that's fun to add them together to check the difference between them.
增加普通的binary search对比一下
class Solution { public: int search(int A[], int n, int target) { return unordBiSearch(A, 0, n-1, target); } int unordBiSearch(int A[], int low, int up, int tar) { if (low > up) return -1; int mid = (low+up)>>1; if (A[mid] == tar) return mid; if (A[mid]>A[up]) { if (A[low] <= tar && A[mid] > tar) return biSearch(A, low, mid-1, tar); else return unordBiSearch(A, mid+1, up, tar); } if (A[mid]<A[up]) { if (A[mid] < tar && A[up] >= tar) return biSearch(A, mid+1, up, tar); else return unordBiSearch(A, low, mid-1, tar); } return -1; } int biSearch(int A[], int low, int up, int key) { if(low>up) return -1; int mid = (low+up)>>1; if (key < A[mid]) return biSearch(A, low, mid-1, key); else if (A[mid] < key) return biSearch(A, mid+1, up, key); return mid; } };
相关文章
- Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))
- Java实现 LeetCode 540 有序数组中的单一元素(位运算入门)
- Java实现 LeetCode 307 区域和检索 - 数组可修改
- SQL Server实现 LeetCode 178 分数排名
- Java实现 LeetCode 33 搜索旋转排序数组
- LeetCode-1144. 递减元素使数组呈锯齿状【贪心,数组】
- 【LeetCode 26】删除排序数组中的重复项
- Leetcode 525. 连续数组
- 【Leetcode刷题Python】33. 搜索旋转排序数组
- 【Leetcode刷题Python】279. 完全平方数
- 【Leetcode刷题Python】103. 二叉树的锯齿形层序遍历
- 【LeetCode】数组中第K大的元素