public class SearchInShiftedArray {
/**
* 题目:给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数。
* 请在这个特殊数组中找出给定的整数。
* 解答:
* 其实就是“旋转数组”。旋转数组的最小元素见http://bylijinnan.iteye.com/blog/1431531
* 采用类似二分查找的策略。首先比较a[0]和a[N/2],如果a[0] < a[N/2],则说明a[0,1,...,N/2]为递增子序列,否则另一部分是递增子序列。
* 然后判断要找的整数是否在递增子序列范围内。如果在,则使用普通的二分查找方法继续查找;如果不在,则重复上面的查找过程,直到找到或者失败为止。
*
*/
public static void main(String[] args) {
int[][] a={
{1,2,3,4,5},
{2,3,4,5,1},
{3,4,5,1,2},
{4,5,1,2,3},
{5,6,1,2,3,4},
};
for(int[] each:a){
int pos=find(each,0,each.length-1,4);
System.out.println(pos);
}
}
public static int find(int[] data,int low,int high,int target){
if(data==null||data.length==0){
return -1;
}
int len=data.length;
if(!(low>=0&&low<len&&high>=0&&high<len)){//0<=(low,high)<=len-1
return -1;
}
int mid=0;
while(low<=high){
if(data[low]<=data[high]){//if 'data' is already increasing
return binarySearch(data,low,high,target);
}
mid=(low&high)+(low^high)/2;
if(data[low]<=data[mid]){//if the first part is increasing
if(target>=data[low]&&target<=data[mid]){
return binarySearch(data,low,mid,target);
}else{
return find(data,mid,high,target);
}
}
if(data[mid]<=data[high]){//if the second part is increasing
if(target>=data[mid]&&target<=data[high]){
return binarySearch(data,mid,high,target);
}else{
return find(data,low,mid,target);
}
}
}
return -1;
}
public static int binarySearch(int[] data,int low,int high,int target){
if(data==null||data.length==0){
return -1;
}
int mid=0;
while(low<=high){
mid=(low&high)+(low^high)/2;
if(data[mid]==target){
return mid;
}else if(data[mid]<target){
low=mid+1;
}else{
high=mid-1;
}
}
return mid;
}
}
分享到:
相关推荐
数组 - 需要参加面试的人
JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA...
01-Java公司面试真题 02-Java面试文档 03-大数据面试文档 04-Java必知必会108题01-Java公司面试真题 02-Java面试文档 03-大数据面试文档 04-Java必知必会108题01-Java公司面试真题 02-Java面试文档 03-大数据面试...
JAVA-SSH面试题;JAVA-SSH面试题;JAVA-SSH面试题
最新各大公司企业真实面试题-Java面试题最新各大公司企业真实面试题-Java面试题
Java-常见面试题.pdf
java java_leetcode面试题解哈希表第349题两个数组的交集_题解
java java_leetcode面试题解哈希表第350题两个数组的交集II_题解
java面试-Java+最常见的+200++面试题汇总+答案总结汇总 java面试-Java并发编程最全面试题 123道 java面试-Java集合框架常见面试题 java面试-Java虚拟机(JVM)面试题 51道 java面试-Kafka知识汇总 18道 java面试-...
java-android面试题
JAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docx
2024最新java-SSHM面试题整理.zip2024最新java-SSHM面试题整理.zip
JAVA-项目面试题.docx
Java-Redis面试题
Java常见面试题集--面试题全面综合
经典sql-java面试题.rar经典sql-java面试题.rar经典sql-java面试题.rar经典sql-java面试题.rar
1.数组求和?(用递归,只用一行代码) 2.求数组的最大值和最小值(用递归的方法,将数组分为左右两个子数组,返回条件是左右数组只剩一个或两个元素)