1.二分法查找。
思想：假設(shè)數(shù)據(jù)是按升序排序的澎粟，對(duì)于給定值 x蛀序，從序列的中間位置開(kāi)始比較，如果當(dāng)前位置值等于 x活烙，則查找成功徐裸；若 x 小于當(dāng)前位置值，則在數(shù)列的前半段中查找啸盏；若 x 大于當(dāng)前位置值則在數(shù)列的后半段中繼續(xù)查找重贺，直到找到為止气笙。
時(shí)間復(fù)雜度：遞歸O(log2n) ? 非遞歸O(log2n)
空間復(fù)雜度：遞歸O(log2n) ? 非遞歸O(1)
要求：必須是有序的序列贫贝，不重復(fù)崇堵。
代碼實(shí)現(xiàn)(java)
/** 二分法查找算法實(shí)現(xiàn)(非遞歸)
* 找到返回目標(biāo)數(shù)字
* 未找到則返回－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.接下來(lái)我們?cè)诶^續(xù)回到旋轉(zhuǎn)數(shù)組中最小值這個(gè)問(wèn)題上面也搓。什么是旋轉(zhuǎn)數(shù)組傍妒？書上的解釋是這樣的，將一個(gè)數(shù)組中的前面若干個(gè)元素，搬到數(shù)組的末尾，就是旋轉(zhuǎn)數(shù)組又谋。直接上代碼看個(gè)明白衰齐。
public class TestA{
public static void main(String[]args){
inta[]={1,0,1,1,1,1};
System.out.println(findMinValue(a));
}/**
* 什么是旋轉(zhuǎn)數(shù)組，例如數(shù)組｛3,4,5,1,2｝ 旋轉(zhuǎn)后變成｛1,2,3,4,5｝就是一個(gè)旋轉(zhuǎn)澈蟆。
*
* */
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;
}
}
