Java 查找算法
顺序查找
原理 顺序查找就是按顺序从头到尾依次往下查找，找到数据，则提前结束查找，找不到便一直查找下去，直到数据最后一位。
图例说明 原始数据：int[] a={4,6,2,8,1,9,0,3}; 要查找数字：8
代码
public class Search {
public static void main(String[] args){
int[] list = {4,6,2,8,1,9,0,3};
Scanner input = new Scanner(System.in);
System.out.println("请输入你要查找的数：");
//存放控制台输入的语句
int num = input.nextInt();
//调用searc()方法，将返回值保存在result中
int result = search(list, num);
if (result == -1) {
System.out.println("你输入的数不存在数组中");
} else {
System.out.println("你输入的数字在数组中的位置是：" + (result + 1) + "个");
}
}
public static int search(int[] list, int num) {
for(int i = 0; i < list.length; i++) {
if(list[i] == num){//如果数据存在
return i;//返回数据所在的下标，也就是位置
}
}
return -1;//不存在的话返回-1
}
}二分查找
原理 算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小 于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
二分算法步骤描述
① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2 ② 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功 若大于，则在右半个区域继续进行折半查找 若小于，则在左半个区域继续进行折半查找 ③ 对确定的缩小区域再按折半公式，重复上述步骤。
image.png
代码
public class BinarySearch {
public static void main(String[] args) {
int list[] = {1, 2, 3, 4, 5, 6, 7, 8};
Scanner scanner = new Scanner(System.in);
System.out.print("输入要查找的数据：");
int key = scanner.nextInt();
int result = binarySearch(list, list.length, key);//返回数据所在位置
if (result == -1) {
System.out.println("你输入的数不存在数组中");
} else {
System.out.println("你输入的数字存在数组中的位置是：" + result + "个");
}
}
private static int binarySearch(int[] list, int length, int key) {
int left = 0;
int right = length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (list[mid] == key) {
return mid;
} else if (list[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;//未找到返回-1
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.03.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录