[Algorithm] 선형검색 이진검색

검색알고리즘을 공부하며 정리해보았다.

출처 : https://velog.io/@kim-jaemin420/%EC%84%A0%ED%98%95-%EA%B2%80%EC%83%89%EA%B3%BC-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89

 

검색

검색에 있어서 키란 찾는 항목을 말한다.

 

종류

검색의 종류는 크게 3가지 배열검색, 연결리스트검색, 이진검색트리검색 등이 있다.

여기서, 배열검색에는 선형 검색, 이진 검색, 해시법 등이 존재한다.

 

선형검색

선형검색이란 (1xn)의 모양으로 늘어진 배열에서 검색할 때 원하는 키를 맨 왼쪽에서 맨오른쪽으로 한 칸씩 이동하며 찾는 검색방법이다.

 

선형검색의 종료조건은 크게 2 가지가 있다.

 

1. 배열에서 키 값을 가진 원소를 못찾고 지나간 경우 (검색에 실패한 경우)

2. 배열에서 키 값을 가진 원소를 찾은 경우 (검색에 성공한 경우)

 

배열의 개수가 n이라면 조건을 판단하는 횟수는 평균 n/2이다.

 

선형검색을 수행하면 배열의 매 원소를 지나갈 때마다 1번과 2번을 확인해야 한다. 따라서, 효율적이지 않음을 알 수 있다.

이를 보완한 것이 보초법이다.

보초법

보초법이란 (1xn)의 모양으로 늘어진 배열에서 검색할 때 맨 오른쪽에 키 값을 원소로 넣어준 후 맨 왼쪽에서 맨 오른쪽으로 한 칸씩 이동하며 찾는 검색방법이다. 여기서, 키 값을 원소로 넣어준 것을 보초라고 한다.

 

보초법을 수행하면 선형검색에서의 종료조건 1을 확인하지 않아도 된다. 따라서, 선형검색에 비해 효율적이라고 할 수 있다.

 

 

예전에 이런 게임을 해보았을 것이다. 1부터 100사이의 자연수를 한 사람이 정하고 다른 사람이 맞춘다. 또한, 숫자를 추측하여 말하였을 때 그 숫자보다 큰지 적은지 말해준다. 어떻게 해야 적은 횟수안에 답을 맞출 수 있는지 고민해보았다면 그 방법이 아마도 이진검색일 것이다.

 

 

이진검색

이진 검색은 (1xn)의 모양으로 늘어진 배열에서 데이터가 정렬되어 있을 때 효율적인 알고리즘이다.

 

방식은 다음과 같다.

1. 배열의 중앙의 값을 고르고 그 원소의 값과 키의 값을 비교한다.

2. 키의 값보다 중앙 원소의 값이 더 큰 경우 맨 처음 원소부터 중앙 원소까지를 기점으로 중앙의 값을 고르고 그 원소의 값과 키의 값을 비교한다.

3. 키의 값보다 중앙 원소의 값이 더 작은 경우 중앙 원소부터 맨 끝 원소를 기점으로 중앙의 값을 고르고 그 원소의 값과 키의 값을 비교한다.

 

위와 같은 1~3 방법으로 쭈욱 진행하여 키 값을 찾는 방식이다.

 

이진 검색의 평균 비교횟수는 log(n)이다.

 

이진 검색의 종료 조건은 크게 2가지가 있다.

1. 중앙의 값과 키의 값이 일치하는 경우

2. 찾는 범위가 역전 되는 경우

 

 

 

 

참고서적

- Bohyoh Shibata,『자료구조와 함께 배우는 알고리즘 입문 파이썬 편』, 이지스퍼블리싱(2020), p.109~130

 

 

 

 

-히비스서커스-