练习2—数据查找

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目

有一组数12，56，45，78，90，80，23，16，8，63 保存在一个数组中，从键盘任意接收一个数，并在数组中查找该数给出是否找到的信息。如果找到了，要求输出该数在数组中所处的位置；如果找不到，输出没有找到的提示信息。

解题步骤

（1）接收；
（2）查找数据；
（3）对比；
（4）输出结果；

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;

public class Demo {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] array = {12, 56, 45, 78, 90, 80, 23, 16, 8, 63};
        System.out.print("please enter the data you are looking for:");
        int user = input.nextInt(), i;
        for (i = 0; i <= 9; i++) {
            if (user == array[i]) {
                System.out.println(user + " " + "is element" + "[" + i + "]");
                break;
            }
            if (i == 9)
                System.out.println("no data " + user + " " + "found");
        }
        input.close();
    }
}

C语言

顺序查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int main()
{
    int array[] = {12, 56, 45, 78, 90, 80, 23, 16, 8, 63}, TakeOver, Tag;
    printf("please enter any data:");
    scanf("%d", &TakeOver);
    for (int i = 0; i < 10; i++)
    {
        if (TakeOver == array[i])
        {
            printf("data %d location is array[%d];", TakeOver, i);
            Tag = 1;
            break;
        }
        else
            Tag = 0;
    }
    if (Tag == 0)
        printf("did not find %d", TakeOver);
    return 0;
}
  1. 本题关于“未找到信息的输出”，我们还可以这样想：如果一组数据，比对到最后一个都没有满足条件的，那么就认定为队列中没有该数据。
  2. 用这样的思想我们可以进行这样的改动：删除Tag标签，增加条件判断直接输出。这里注意变量i的自增，为了在i=10时仍能进入循环输出信息，判断条件应修改为i <= 10。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

int main()
{
    int array[] = {12, 56, 45, 78, 90, 80, 23, 16, 8, 63}, TakeOver;
    printf("please enter any data:");
    scanf("%d", &TakeOver);
    for (int i = 0; i <= 9; i++)
    {
        if (TakeOver == array[i])
        {
            printf("data %d location is array[%d];", TakeOver, i);
            break;
        }
        if (i == 9)
            printf("data %d was not found", TakeOver);
    }
    return 0;
}

说明

  1. 本题中最重要的是如何将已有数据和用户输入数据进行对比，也就是 “查找” 这一操作，代码1给出的是查找算法中最简单的 “顺序查找” 。
  2. 由于每次进入循环，变量i依次自增、逐个查找，如果我们仅仅只将单一的输出信息放在语句中而不进行其它判断的话，就会造成输出错误。所以增加变量Tag用于判断条件：如果数据相等（找到了），Tag值置 1 。如果没有找到，Tag值置0，循环外进行一次判断输出没有找到的提示信息。
  3. 我竟然试图用二分法解决，但是却忽略了使用二分（折半）查找的前提必须是有序表顺序存储。这里给出两种版本的二分法，注意算法适用条件。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int Search1(int a[], int value, int n)
{
    int low, high, mid;  //定义最低位,最高位,中间位
    low = 0;
    high = n-1;   //数据从0开始,则最后一个为n-1,总数仍为n
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)    //中间值和待查找值相等,直接返回
            return mid;
        if(a[mid]>value)     //中间值大于待查找值,待查找值在中间值左边,最高位high置为mid-1
            high = mid-1;
        if(a[mid]<value)     //中间值小于待查找值,待查找值在中间值右边,最低为low置为mid+1
            low = mid+1;
    }
    return -1;
}
 
//递归版本
int Search2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;      //组中值 mid=(low+high)/2等价于mid=low+1/2*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return Search2(a, value, low, mid-1);  //函数递归调用
    if(a[mid]<value)
        return Search2(a, value, mid+1, high);
}