1.二分法查找。
思想：假设数据是按升序排序的，对于给定值 x，从序列的中间位置开始比较，如果当前位置值等于 x，则查找成功；若 x 小于当前位置值，则在数列的前半段中查找；若 x 大于当前位置值则在数列的后半段中继续查找，直到找到为止。
时间复杂度：递归O(log2n) 非递归O(log2n)
空间复杂度：递归O(log2n) 非递归O(1)
要求：必须是有序的序列，不重复。
代码实现(java)
/** 二分法查找算法实现(非递归)
* 找到返回目标数字
* 未找到则返回－1
* Created by Darker on 15/7/17.
*/
public class TestA{
public static void main(String[]args){
inta[]={1,2,3,4,5,6};
System.out.println(findData(a,4));
}
public static int findData(int[]a,intx){
int start=0;
int end=a.length-1;
while(start<=end){
int middle=(start+end)/2;
if(x==a[middle]){
return a[middle];
}else
{
if(x
end=middle-1;
}else{
start=middle+1;
}
}
}
return-1;
}
}
2.接下来我们在继续回到旋转数组中最小值这个问题上面。什么是旋转数组？书上的解释是这样的，将一个数组中的前面若干个元素，搬到数组的末尾，就是旋转数组。直接上代码看个明白。
public class TestA{
public static void main(String[]args){
inta[]={1,0,1,1,1,1};
System.out.println(findMinValue(a));
}/**
* 什么是旋转数组，例如数组｛3,4,5,1,2｝ 旋转后变成｛1,2,3,4,5｝就是一个旋转。
*
* */
public static int findMinValue(inta[]){
if(a.length!=0){
int start=0;
intend=a.length-1;
int middle=start;
while(a[start]<=a[end]){
if(end-start==1){
middle=end;
break;
}
middle=(start+end)/2;
if(a[start]==a[end]&&a[middle]==a[start])
return minInOrder(a,start,end);
if(a[middle]>=a[start]){
start=middle;
}else if(a[middle]<=a[end]){
end=middle;
}
}
return a[middle];
}else{
return-1;
}
}
/**
* 顺序查找
* */
public static int minInOrder(int a[],int start,int end){
int result=a[start];
for(inti=start+1;i<=end;i++){
if(result<=a[i])
result=a[i];
}
return result;
}
}
网友评论