循环有序数组查找
循环有序数组查找
- 题目:循环有序数组就是类似于56781234这样的数组。用logn复杂度查找一个元素,并返回其下标;如果不存在则返回-1.
- 思路:有序数组容易想到二分查找。但是需要加一些细节判断。
- 第一种情况:mid值落在前半部分有序数组中,那么继续判断要查找的n是否落在start和mid中间有序数组部分:是,那么end=mid-1;否则start=mid+1,向后半部分区域查找
- 第二种情况:mid值落在后半部分有序数组,通过a[mid]>a[start]可以判断,继续判断n是否落在mid和end之间:是,那么start=mid+1,否则end=mid-1,向前寻找。
- 要注意的是除了要判断a[mid]是否等于n之外,还要判断a[start]和a[end]。
public static int binarySearch(int a[],int n) {
if(a==null||a.length==0)
return -1;
int start=0,end=a.length-1;
int mid=(start+end)/2;
while(start<=end) {
if(a[start]==n)
return start;
if(a[end]==n)
return end;
if(a[mid]==n)
return mid;
mid=(start+end)/2;
if(a[start]<a[mid]) {
if(a[start]<n&&a[mid]>n)
end=mid-1;
else
start=mid+1;
}else {
if(a[mid]<n&&n<a[end])
start=mid+1;
else
end=mid-1;
}
}
return -1;
}
本文标题:循环有序数组查找
本文链接:https://www.haomeiwen.com/subject/gtsssqtx.html
网友评论