简单查找算法(java实现)
程序员文章站
2024-03-16 10:02:22
...
线性查找
线性查找又称顺序查找,是一种最简单的查找方法,时间复杂度为O (n)它的基本思想是从第一个记录开始,逐个比较记录的关键字,直到和给定的目标值相等,则查找成功;若比较结果与文件中n个记录的关键字都不等,则查找失败。
package com.wzc;/*
*@date 2021/3/1
* @author wzc
*/
import java.util.Arrays;
import java.util.Scanner;
//线性查找
public class SearchTest {
public static void main(String[] args) {
int[] arr = {5, 3, 45, 34, 24, 87};
System.out.println("原数组是" + Arrays.toString(arr));
System.out.println("请输入数字");
Scanner sc = new Scanner(System.in);
int target = sc.nextInt();
search(arr, target);
}
public static void search(int[] arr, int target) {
//令指针为-1
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (target == arr[i]) {
index = i;
break;
}
}
//指针为发生变化,说明没找到目标数字,直接返回
if (index == -1) {
System.out.println("未查找到目标数字");
return;
}
System.out.println("你所查找的目标在第" + (index + 1) + "个位置");
}
}
编译结果:
二分查找法
又称为折半查找,二分查找适合对已经排序好的数据集合进行查找,时间复杂度O(log2 n),效率高。假设有一升序的数据集合,先找出升序集合中最中间的元素,将数据集合划分为两个子集,将最中间的元素和目标关键字进行比较,,如果等于关键字则返回,如果大于关键字,则在前一个数据集合中查找,否则在后一个子集中查找,直到找到为止,如果没找到则返回。
package com.wzc;/*
*@date 2021/3/1
* @author wzc
*/
import java.util.Arrays;
import java.util.Scanner;
//二分查找
public class BinarySearchTest {
public static void main(String[] args) {
//使用二分查找前提条件必须是数组有序
int[] arr = {1, 2, 5, 6, 36, 48};
System.out.println("原数组顺序是"+ Arrays.toString(arr));
int begin = 0;
int end = arr.length-1;
System.out.println("请输入数字");
Scanner sc = new Scanner(System.in);
int target = sc.nextInt();
binarySearch(arr,begin,end,target);
}
public static void binarySearch(int[] arr, int begin, int end, int target) {
int index = -1;
while (begin<=end){
int mid = (begin+end)/2;
if (arr[mid] == target){
//找到目标数字
index = mid;
break;
}else{
if (arr[mid] <= target){
begin = mid + 1;
}else{
end = mid -1;
}
}
}
if (index == -1){
System.out.println("未找到该目标数字");
return;
}
System.out.println("目标在第"+(index+1)+"个位置");
}
}
编译结果: