[자료구조] 22 순차탐색

📌탐색

다수의 레코드 집합에서 특정 키 값과 일치하는 레코드 찾는 작업 

✔️레코드

객체(object)의 속성(property)에 해당하는 필드(field)의 집합 

✔️리스트

레코드의 집합

✔️디스크

리스트가 파일형식으로 저장되는 곳 

 

📌순차탐색 (Sequential Search)

목표 키를 찾을 때까지 순차적으로 비교 반복 

❗️최상 : 첫번째 비교에서 목표 레코드 찾는 경우 , 비교 횟수 1번

💢최악 : 가장 마지막 비교에서 목표 레코드 찾는 경우 , 비교 횟수 n번

시간 복잡도 : O(n)

import java.util.Scanner;

public class Sequential {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int pos = 0;
        int n = sc.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }
        int key = sc.nextInt();
        pos = seq_search(num, key, n);
        if(pos == -1){
            System.out.println("There's no key!");
        }
        else {
            System.out.println(pos);
        }
    }
    public static int seq_search(int num[], int key, int n){
        int i;
        for (i=0; i<n; i++){
            if(key == num[i]){
                return i;
            }
        }
        return -1;
    }
}

👆👆Java code 입니다.. 지금까진 C!

 

👉입력..

처음에 입력 받을 배열안의 원소 수 : num

원소 수 입력 받고 

key로 찾고자 하는 원소 입력

10
12 5 6 19 21 3 7 81 42 15
81

👉출력..
7

num[7]에 key가 있다!