欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

简单查找算法(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) + "个位置");
    }
}

编译结果:
简单查找算法(java实现)

二分查找法

又称为折半查找,二分查找适合对已经排序好的数据集合进行查找,时间复杂度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)+"个位置");
    }
}

编译结果:
简单查找算法(java实现)