查找算法
eaaomk 2021-12-25 23:00:00 Java
# 折半查找 & 二分查找
折半查找(Binary Search)又称为二分查找，其要求数据序列呈线性结构，也就是经过排序的。对于没有经过排序的，可以查阅我之前的排序算法文章进行预排序，然后进行折半查找操作。
譬如数组{1，2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
1.第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找，
2.寻找{6， 7， 8， 9}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
二分查找算法就是不断将数组进行对半分割，每次拿中间元素和目标数据进行比较。
public class BinarySearch {undefined
public static void main(String[] args) {
int a[]={1,2,3,4,5,6,7,8};
Scanner sca=new Scanner(System.in);
System.out.print("输入要查找的数据：");
int x=sca.nextInt();
int loc=binarySearch(a,a.length,x);//返回数据所在位置
System.out.print(loc);
}
private static int binarySearch(int[] a, int length, int x) {
int left=0;
int right=length-1;
int mid;
while(left<=right){
mid=(left+right)/2;
if(a[mid]==x){
return mid;
}
else if(a[mid]>x){
right=mid-1;
}else{
left=mid+1;
}
}
return -1;//未找到返回-1
}
}
# 哈希查找
- 请读者移步HashMap相关文章
# 树查找
- 请读者移步二叉树/红黑树相关文章