선형탐색(Linear search)
- 순차탐색임
- 순차 탐색: 배열에 있는 특정한 원소를 찾기 위하여 배열의 처음 원소부터 차례로 모든 원소들을 비교하여 탐색함
- 모든 원소를 조사하는 탐색을 선형탐색(Linear search)라고 함
- O(n) 알고리즘
알고리즘 개요
- 프로그램에서 for 문을 제외하면 다른 문장은 한번만 수행함
- for문에서의 비교 횟수를 조사함으로써 전체 수행횟수를 알 수 있음
- 찾는 원소가 배열에 없는 경우 : n+1 번 비교
- 찾는 원소가 맨 처음에 있는 경우 : 1번 비교
- 찾는 원소가 원래 배열의 마지막에 있는 경우 : n번 비교
- 평균 비교 횟수
-> 대부분 for문의 개수 1개단 n으로 봄(이중 for문: \(n^2\))
코드
수도코드
파이썬
def Linear_search(input_list, find_num):
num = len(input_list)
for i in range(0,num):
if input_list[i] == find_num:
return i # 찾으면 위치를 돌려줌
# 주어진 리스트를 모두 찾아봤는데 찾는 함수가 없으면 -1 돌려줌
return -1
#----- 실행함수------
a = [8,10,2,7,5,9,0]
## 만약 9을 찾고 싶다면
print(Linear_search(a, 9))
## 만약 7을 찾고 싶다면
print(Linear_search(a, 7))
## 만약 28을 찾고 싶다면
print(Linear_search(a, 28)) # 없으므로 -1이 나옴
자바
package search;
import java.util.Scanner;
public class SSearch{
public static int Linear_search(int[] arr, int find_num) {
//순서대로 비교하기 위해 배열의 크기만큼 반복
for (int i = 0; i < arr.length; i++) {
if (arr[i] == find_num) //비교할 데이터가 배열에 있으면 배열의 위치를 return
return i;
}
return -1; // 없다면 -1을 return
}
//----- 실행함수------
public static void main(String[] args) {
int[] input_list = {8,10,2,7,5,9,0};
## 만약 9을 찾고 싶다면
int find_num = 9
int result = sequentialSearch(input_list, find_num);
}
}