精华内容
下载资源
问答
  • 使用折半查找法查找数组中的元素

    千次阅读 2018-07-24 09:46:29
     /*进行折半查找操作*/  if(addr != -1) { /*返回值为不为-1,查找成功*/  printf("key[%d] = %d\n ",addr,k);  }else {  printf("There is no %d in array key\n",k); /*返回值为-1,查找失败*/  } ...

    #include "stdio.h"
    int bin_search(int key[],int n,int k)
    {
        int  low = 0, high = n-1, mid;
        while(low<=high){
            mid = (low+high)/2;
            if(key[mid] == k) {
                return mid;        /*查找成功,返回mid*/
            } if (k > key[mid]) {
                low = mid + 1;        /*在后半序列中查找*/
            } else {
                high = mid - 1;        /*在前半序列中查找*/
            }
        }
        return -1;                    /*查找失败,返回-1*/
    }

    int bin_search_recur(int key[],int low, int high,int k)
    {
        int mid;

        if(low>high)
            return -1;
        else{
            
            mid = (low+high) / 2;
            if(key[mid]==k) {
                return mid;
            }
            if(k>key[mid]) {
                return bin_search_recur(key,mid+1,high,k);        /*在序列的后半部分查找*/
            } else {
                return bin_search_recur(key,low,mid-1,k);            /*在序列的前半部分查找*/
            }    
        }
    }


    main()
    {
        int key[10] = {1,3,5,7,10,12,15,19,21,50};    /*初始化一个整型数组*/
        int i,n ,addr;
        int k;
        printf("The contents of the Array key are\n");
        for(i=0;i<10;i++) {
            printf("%d ",key[i]);                    /*显示关键字数组key中的内容*/
        }
        printf("\nInput a interger for search\n");
        scanf("%d",&k);                                /*输入待查找的元素k*/
        addr = bin_search(key,10,k);                /*进行折半查找操作*/
        if(addr != -1) {                            /*返回值为不为-1,查找成功*/
            printf("key[%d] = %d\n ",addr,k);
        }else {
            printf("There is no %d in array key\n",k);        /*返回值为-1,查找失败*/
        }
        
        addr = bin_search_recur(key,0,9,k);
        if(addr != -1) {                            /*返回值为不为-1,查找成功*/
            printf("key[%d] = %d\n ",addr,k);
        }else {
            printf("There is no %d in array key\n",k);        /*返回值为-1,查找失败*/
        }
        getchar();
        getchar();
    }

    展开全文
  • 折半查找法 折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素...

    折半查找法

    折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
    搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

    //实现在主函数内部

    #define _CRT_SECURE_NO_WARNINGS 1
    //折半查找法
    
    //实现在主函数内部
    #include<stdio.h>
    int main()
    {
    	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    	int left = 0;
    	int right = sizeof(arr) / sizeof(arr[0] - 1);//数组的下标是从0开始,所以要数组长度-1
    	int key = 0;
    	int mid = 0;
    	printf("请输入你要查找的数字(1—10):\n");
    	scanf("%d", &key);
    	while (left <= right)//当左下标小于等于右边进入循环
    	{
    		mid = (left + right) / 2;
    		if (arr[mid] > key)
    		{
    			right = mid - 1;
    		}
    		else if (arr[mid] < key)
    		{
    			left = mid + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    	if (left <= right)//循环结束后,当左下标<=右下标的时候,说明找到了
    		printf("找到了,数字%d的下标是%d\n", arr[mid],mid);
    	else//当左>右的时候,证明已经找了一遍,则数组中没有要找的元素
    		printf("找不到%d\n",key);
    	return 0;
    }
    

    在这里插入图片描述

    //折半查找函数实现

    //折半查找函数实现
    #include<stdio.h>
    
    int BinSearch(int arr[], int left, int right, int key)//折半查找函数,参数列表 接收数组,左右下标,要查找到的值
    {
    	int mid = 0;
    	while (left <= right)
    	{
    		mid = (left + right) / 2;
    		if (arr[mid] > key)
    		{
    			right = mid - 1;
    		}
    		else if (arr[mid] < key)
    		{
    			left = mid + 1;
    		}
    		else
    		{
    			return mid;//arr[mid]=key 时返回mid下标
    		}
    	}
    	return -1;//循环结束还没有找到目标值,返回-1
    
    }
    int main()
    {
    	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    	int  left = 0;
    	int right = sizeof(arr) / sizeof(arr[0]) - 1;
    	int key = 0;
    	printf("请输入一个数字(1—10):\n");
    	scanf("%d", &key);
    	int k = BinSearch(arr, left, right, key);//调用函数
    	if (k == -1)//判断k的值 检测是否找到
    	{
    		printf("找不到%d\n",key);
    	}
    	else
    	{
    		printf("找到了,数字%d的下标是%d\n", key, k);
    	}
    	return 0;
    }
    

    在这里插入图片描述

    展开全文
  • 顺序查找举例:查找数组中是否存在值 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。

    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
    折半查找
    能使用折半查找的前提是数组中的数据是有序的。

    折半查找的原理:
    假设查找的数组区间为 [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]。

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

    折半查找举例:查找数组中是否存在等于 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
    顺序查找和折半查找
    在查找速度方面,顺序查找自然是不及折半查找,我们代码中数组的长度比较小,没有太大差距,当数据量较大时,我们就能明显感觉到运行时间差距了。

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

    编程要求
    仔细阅读右侧编辑区内给出的代码框架及注释,在 Begin-End 间编写程序代码,使用折半方法查找数组中某元素的索引,并统计出查找次数,具体要求如下:

    接收给定的数据(如: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 **********/
            // 定义变量
          Scanner sc = new Scanner(System.in);
          int n = sc.nextInt();
          int m = sc.nextInt();
          int a[] = new int[n];
            // 接收给定数据
            for(int i=0;i<n;i++){
                a[i] = sc.nextInt();
            }
            // 定义数组
            for(int i=0;i<n-1;i++){
                for(int j=0;j<n-i-1;i++){
                    if(a[j]>a[j+1]){
                        int t = a[j+1];
                        a[j+1] = a[j];
                        a[j] = t;
                    }
                }
            }
            int max = a.length-1;
            int min = 0;
            int mid= (max+min)/2;
            int i=0;
            int flag = 0;
            int count=1;
            while(true){
                if(m<a[mid]){
                    max=mid-1; 
                }
                else if(m>a[mid]){
                    min = mid +1;
                }
                else{
                    System.out.printf("索引值:%d。查找次数:%d。",mid,count);
                    break;
                }
                count++;
                if(max<min){
                  System.out.println("没有找到");
                  break;
            }
            mid =(max + min)/2;
            }
            
           
    	
            /********** End **********/
        }
     }
    
    
    
    展开全文
  • 折半法 数组查找

    2020-02-02 18:06:03
    题目:有15个数按由小到大顺序存放在一个数组中,输入一个数,要求用折半法查找出该数是数组中的第几个元素的值。如果该数不在数组中,则输出“无此数”。 注意:存在 scanf("%d",&number); scanf(" %c",&c)...

    题目:有15个数按由小到大顺序存放在一个数组中,输入一个数,要求用折半法查找出该数是数组中的第几个元素的值。如果该数不在数组中,则输出“无此数”。

    注意:存在
    scanf("%d",&number);
    scanf(" %c",&c);
    第二个输入语句的条件控制要加空格,因为上一个结束标记是回车,这个时候在输入缓存里就把这个回车字符存在里面了。当你要再读入一个字符时,
    就会默认先把缓存里的回车符读入(如果不加空格)

    #include<stdio.h>
    #define  N 15
    int main()
    {
    	int i,number,top,bott,mid,flag,loca,sign,a[N]={0};
    	char c;
    	printf("enter date:\n");
    	scanf("%d",&a[0]);							//输出第一个数
    	i=1;
    	while(i<N)									//是否输入完毕
    	{
    		scanf("%d",&a[i]);
    		if(a[i]>=a[i-1])						//判断输出的数是不是比前一个大
    			i++;
    		else
    			printf("enter this data again:\n");
    	}
    	printf("\n");
    	for(i=0;i<N;i++)							//输出数组
    		printf("%5d",a[i]);					
    	printf("\n");
    	while(flag)
    	{
    		printf("input number to look for:");
    		scanf("%d",&number);         			//输入要查找的数
    		top=0;									//查找区间的起始位置
    		bott=N-1;								//查找区间的最末位置
    		loca=0;sign=0;							//表示是否存在
    		if(number<a[0] || number>a[N-1])		//判断是否在区间内
    			loca=1;
    		else
    			while(top<=bott)					//循环查找条件
    			{
    				mid=(bott+top)/2;				//中间元素下标
    				if(number==a[mid])				
    				{
    					printf("Has found %d, its position is %d\n",number,mid+1);
    					sign=1;
    					break;
    				}
    				else if(number>a[mid])			//如果数大于中间下标
    					top=mid+1;					//在mid+1~bott中寻找
    				else
    					bott=mid-1;					//否则在top~mid-1中寻找
    			}
    		if(loca || !sign)						//判断是否存在
    			printf("cannot find %d.\n",number);
    		printf("continue or not(Y/N)?");		//提示是否继续查找
    		scanf(" %c",&c);						//注意:有空格
    		if(c=='n'||c=='N')
    			flag=0;
    	}
    
    	return 0;
    }
    
    展开全文
  • java日常学习:直接查找和二分法(折半法查找数组元素
  • int main() {//用折半查找数组中查找值为x的元素。 int arr[] = {1,2,3,4,5,6,7,8,9,10};//数组必须有序。 int sz = sizeof(arr) / sizeof(arr[0]);//计算数组长度。 int i, x; int left = 0, right = sz - 1;...
  • 折半查找:前提是该数组是有序的数组 */ import java.util.Scanner; public class arrLookup{ public static void main(String[] args){ int[] arr = {1,4,6,8,34,56,78}; Sy...
  • 折半法查找数组中指定数字的位置并返回, 此方法可以减少遍历数组的次数,提高查询效率, 尤其是当数组中数据比较多的时候, 这种方式查询效率更明显, 在数据库查询中多使用此方法
  • 利用折半法查找数组中是否存在该数,并输出查找结果(如果在请输出该数在数组中的位置,如不在请输出不存在)。 程序运行结果示例: 输入:请输入数组的个数: 5 33 66 55 44 88 请输入要查找的数:55 输出:存在排序...
  • 折半查找 假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)/2,X与中点元素mid比较. (1)若X等于mid,即找到,停止...
  • 折半查找法(基于有序数组

    千次阅读 2018-10-07 18:13:25
    折半查找的方法优点: 比较次数少,查找速度快,平均性能好,要求待查表为有序表 存储结构一定是顺序结构 代码实现: #include &amp;lt;stdio.h&amp;gt; #include &amp;lt;stdlib.h&amp;gt; ...
  • 1.用折半查找数组元素的下标2.但前提是数组已经排序好的3.例:public static void main(String ars []){int [] number=new int []{2,6,9,45,65,88};}publci staic int getIndex(int [] arr,int key){ int min=0,max=...
  • c语言 一维数组折半查找法Problem statement: Write a C program to find the second smallest element in a one dimensional array. 问题陈述:编写C程序以查找一维数组中的第二个最小元素。 Example: Type1: ...
  • 折半查找有序数组中的某个元素

    千次阅读 2016-12-02 01:17:17
    #define _CRT_SECURE_NO_WARNINGS 1 #include #include int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 8, 9, ...//数组是已排序的数组,有一定规律 int key=7 ; int left = 0; int right = sizeof(arr) / sizeof(a
  • 算法思想:又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个...
  • 2.有15个数存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出“无此数”。以15个数赋初值的方法在程序中给出。要找的数scanf函数输入。
  • 折半法查找一个整数是否在数组

    千次阅读 2020-03-05 21:24:19
    在一堆无序的数据中寻找数据是困难的,但是对于已排序的数据,就会有比较快捷的方 判断一个数据是否在其中,这里的例子使用折半法判断一个数据是否在一个数组中。折半 的思想非常简单,对于从小到大排序的数组,...
  • 选择排序+循环折半查找法 代码如下:#include<iostream>using namespace std;int main(){ int a[15]; int n,i; void array_sort(int a[], int n); int zeban(int a[], int start ,int end,int n); cout<<...
  • Java和c++中二分法查找数组元素的实现机制 在数据结构和算法中,我们会见到二分法查找数组元素这个经典的算法。事实上,二分法也称为折半查找法。该算法的主要机制是: **(1)**先将数组元素从小到大排列(或者从大...
  • c语言 一维数组折半查找法Problem statement: Write a C program to find two smallest elements in a one dimensional array. 问题陈述:编写一个C程序以在一维数组中找到两个最小的元素。 Example: Type1: (all ...
  • 二分查找(折半查找)——数组中的重复数字二分查找(折半查找数组中的重复数字 二分查找(折半查找) 二分查找是一种算法,其输入是一个有序的元素列表(必须是有序的),如果查找的元素包含在列表中,二分查找...
  • C++数组元素位置的查找程序,对学习数组有一定的帮组
  • 折半查找法 在有序数组中查找时 从数组的中间元素开始查找,如果中间元素正好是要查找的元素,则搜索过程结束, 如果所找元素大于(小于)中间元素,则在数组大于(小于)中间元素的那一半中查找, 每一次跟开始一样...
  • 文章目录前言问题描述输入格式输出格式样例输入样例输出数据规模与约定一、 ...递归函数实现二分法查找数组元素。  补充:要求给定数组采用如下代码定义  int data[200];  for (i=0; i<200; i++)  data[i]=4*
  • 一、最大值查询:定义一个函数接收一个int类型的数组对象,找出数组对象中的最大元素返回给调用者。 1、思路: 2、代码实现: 二、排序算法: 1、选择排序(直接排序): a)定义:使用一个元素与其他的元素逐个...
  • 折半查找的效率比较高,但是前提条件是数组中的元素按序排列。 练习:查找一个元素数组中第一次出现的位置,如果数组中没有此元素,则返回-1; public class ArrayTest3{ public static void main(String[] ...
  • 问题: 给出一组有序的整数,要在这组整数中插入一...不同的是折半查找是查找是否存在元素,而这个要查找位置。public class Index{ public static void main(String args[]) { int[] array={6,14,15,26,32}; in
  • 二分查找(折半查找法):查找数组中是否包含指定元素。如果包含指定元素,则返回指定元素的index(从0开始);如果不包含指定元素,则返回-1; 前提:数组中的元素必须是有序的。 原理: 将被查找的数组分为...
  • c语言 一维数组折半查找法Problem statement: Write a C program to find second largest element in a one dimensional array. 问题陈述:编写C程序以查找一维数组中的第二大元素。 Example: 例: Input : ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,337
精华内容 8,934
关键字:

用折半法查找数组元素