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

顺序查找和折半查找

程序员文章站 2022-03-10 17:15:56
顺序查找和折半查找1.顺序查找2.折半查找1)折半查找的原理:2)折半查找举例:3)举例:使用折半方法查找数组中某元素的索引,并统计出查找次数3.顺序查找和折半查找1.顺序查找顺序查找就是从数组的第一个元素开始,依次比较,直到找到目标数据或查找失败。顺序查找举例:查找数组中是否存在值 432。public class FindTest { public static void main(String[] args) { int i; int[] arr={...

1.顺序查找

顺序查找就是从数组的第一个元素开始,依次比较,直到找到目标数据或查找失败。

顺序查找举例:查找数组中是否存在值 432。

public class FindTest {
    public static void main(String[] args) {
        int i;
        int[] arr={1,2,4,5,54,321,867,432,3};
           for( i=0;i<arr.length;i++){      // 顺序遍历数组中的值
          // 判断是否存在元素432
           if(arr[i]==432){
                System.out.print("目标值的索引为:"+i);
                break;
            }
             if(i==arr.length-1){
                System.out.println("数组中没有对应的值");
            }
         }
    }
}

输出结果:

目标值的索引为:7

2.折半查找

能使用折半查找的前提是数组中的数据是有序的

1)折半查找的原理:

假设查找的数组区间为 [min,max],min 代表起始索引,max 代表结束索引,T 代表需要查找的值。

  • 第一步:确定该区间的中间位置 K;
  • 第二步:将查找的值 T 与 array[k] 比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续折半查找;
  • 第三步:若 array[k]>T,由数组的有序性可知 array[k,k+1,……,max] 中的每个值都大于 T,故新的区间为 array[min,……,K-1],若 array[k]<T,同理可得新的查找区间为 array[k+1,……,max]。

每一次查找与中间值比较,可以确定是否查找成功,不成功的话下一次查找区间将缩小一半。

2)折半查找举例:

查找数组中是否存在等于 80 的元素。

        public static void main(String[] args) {
            int [] arr={5,13,19,21,37,56,64,75,80,88,92};     // 数组必须是有序的    
            // 定义三个变量分别记录最大、最小、中间的查找范围索引值
            int max=arr.length-1;
            int min=0;
            int mid;
            int target=21;
            mid=(max+min)/2;
            while(true) {
                if(target<arr[mid]) {     // 如果目标元素小于中点元素            
                    max = mid-1;     // max向mid前移动
                }
                else if(target>arr[mid]) {     // 如果目标元素大于中点元素     
                    min = mid+1;     // min向mid后移动
                }
                else {
                    System.out.println(mid);     // 找到目标元素
                  break;
                }
                if(max<min) {     // 没有找到的情况
                    System.out.println("没有找到");
                    break;
                }
                mid=(max+min)/2;       // 重新计算中间索引值
            }
        }

执行结果:

3

3)举例:使用折半方法查找数组中某元素的索引,并统计出查找次数

具体要求如下:

接收给定的数据(如:4 88 43 43 98 #…,其中第一个数代表数组长度,第二个数代表需要查找的元素,其余数代表数组元素,# 号用于终止接收数据),遇到 # 号终止接收;
创建数组,使用折半方法查找数组中某元素的索引,并统计出查找次数。

注意:数字分隔符为空格。

测试输入:

6 78 4 34 78 458 488 788 #

预期输出:

索引值:2。查找次数:1。

测试输入:

6 786 4 34 78 458 488 788 #

预期输出:

没有找到

import java.util.Scanner;

public class FindTest {
    public static void main(String[] args) {
		
        // 请在 Begin-End 间编写代码
        /********** Begin **********/
        // 定义变量
        int n,count;
        // 接收给定数据
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        count = input.nextInt();
        // 定义数组
        int a[]= new int[n];
        // 给数组赋值
       for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        // 查找给定元素索引,并输出查找次数                 
        int max=a.length-1;    // 定义三个变量分别记录最大、最小、中间的查找范围索引值
        int min=0;
        int mid;
        int target=count;
        int t=0;   //记录查找的次数
        mid=(max+min)/2;
        while(true) {
            t++;
            if(target<a[mid]) {     // 如果目标元素小于中点元素            
                max = mid-1;     // max向mid前移动                
            }
            else if(target>a[mid]) {     // 如果目标元素大于中点元素     
                min = mid+1;     // min向mid后移动                
            }
            else {               
                System.out.printf("索引值:%d。查找次数:%d。",mid,t);     // 找到目标元素
              break;
            }
            if(max<min) {     // 没有找到的情况
                System.out.println("没有找到");
                break;
            }
            mid=(max+min)/2;       // 重新计算中间索引值
        }
        /********** End **********/
    }
 }

3.顺序查找和折半查找

查找速度方面,顺序查找自然是不及折半查找,我们代码中数组的长度比较小,没有太大差距,当数据量较大时,我们就能明显感觉到运行时间差距了。

从另一方面来说,顺序查找对数据要求不高,无需数据按照某种方式排列,也无需指定存储格式,顺序存储可以,链式存储也可以。所以从应用范围来说,顺序查找算法自然会更好。

本文地址:https://blog.csdn.net/qq_45896330/article/details/110265174

相关标签: java基础 java