首页 > 代码库 > LeetCode-Search in Rotated Sorted Array-旋转数组中的搜索-二分搜索+代数逻辑
LeetCode-Search in Rotated Sorted Array-旋转数组中的搜索-二分搜索+代数逻辑
https://oj.leetcode.com/problems/search-in-rotated-sorted-array/
一个被旋转的数组，要求二分搜索查询一个数。修改二分搜索可以完成。注意可以通过A[l]<A[r]来判断l,r中间数字分布的情况。在A[l]>A[r]时，中间有一个间断点。可以通过A[mid]>A[r]来判断中点与旋转中心的位置关系。然后通过逻辑比较移动l或r。画出一个折线图能够更好的理解。
注意二分搜索终止条件为l<r，更新l位置时始终用l=mid+1。这样能够避免死循环。在退出循环后通过判断A[l]与target关系来确定是否查询到。
class Solution {public: int search(int A[], int n, int target) { int l=0; int r=n-1; int x=target; while(r>l){ int mid=(l+r)/2; if (x==A[mid]) return mid; if (A[l]<A[r]) { if (x<A[mid]) r=mid; else l=mid+1; } else { //Al>Ar if (A[mid]<A[r]) { if (x<A[mid]) r=mid; else { if (x>A[r]) r=mid; else l=mid+1; } } else { if (x>A[mid]) l=mid+1; else { if (x>A[r]) r=mid; else l=mid+1; } } } } if (A[l]==x) return l; return -1; }};
LeetCode-Search in Rotated Sorted Array-旋转数组中的搜索-二分搜索+代数逻辑
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。