public class BinarySearch {
public static void main(String[] args) {
int []arr={1,3,8,66,148,155};
System.out.println(binarySearch(arr,8));
System.out.println(search(arr,0,arr.length-1,8));
System.out.println(sequential_search(arr,8));
}
/**
* 顺序(线性)查找算法
最好查找一次,最差查找n次.平均(n+1)/2
* 时间复杂度:O[n]
* */
public static int sequential_search(int[]arr,int des){
//判断如果查找的值是第一个的话直接返回
if(arr[0]==des){
return 0;
}
arr[0]=des;//哨兵,返回值为0,说明没找到.对for循环的优化
int index=arr.length-1;
//从最后一个元素开始遍历
while(arr[index]!=des){
index--;
}
return index;
}
/**
* 二分查找算法:
* 要求:有序,线性结构
* 时间复杂度O[log(n)]
循环实现
* */
public static int binarySearch(int []arr,int des){
int low=0;
int high=arr.length-1;
while(low<high){
int middle=(low+high)/2;
//先拿中间的值与查找的值比较,大于中间的值,说明查找的值索引在[low,middle)
if(des==arr[middle]){
return middle;
}else if(des<arr[middle]){
high=middle-1;
}else{
high=middle+1;
}
}
return -1;
}
/**
* 二分查找算法:
* 要求:有序,线性结构
* 时间复杂度O[log(n)]
*递归实现
* */
public static int binarySearch(int[]arr,int begin,int end,int des){
if(des<arr[begin]||des>arr[end]||begin>end){
return -1;
}
int middle=(begin+end)/2;
if(des<arr[middle]){
return binarySearch(arr,begin,middle-1,des);
}else if(des>arr[middle]){
return binarySearch(arr,middle+1,end,des);
}else{
return middle;
}
}
/**
* 时间复杂度O[log(n)],好于二分查找
* 插值查找算法
* */
public static int search(int[]arr,int begin,int end,int des){
if(des<arr[begin]||des>arr[end]||begin>end){
return -1;
}
int middle=begin+(end-begin)*(des-arr[begin])/(arr[end]-arr[begin]);//和二分法的区别,就是在查找区间的选择上
if(des<arr[middle]){
return binarySearch(arr,begin,middle-1,des);
}else if(des>arr[middle]){
return binarySearch(arr,middle+1,end,des);
}else{
return middle;
}
}
}