목차
1. 검색(Search) 알고리즘
배열 등의 데이터에서 특정 값을 검색하는 알고리즘.
일반적으로 순차 검색, 이진 검색으로 구분할 수 있다.
- 순차 검색(Sequencial Search) : 전체 데이터를 처음부터 끝가지 순서대로 검색
- 이진 검색(Binary Search) : 정렬되어 있는 데이터를 절반으로 나눠 검색.
1.1 이진검색 알고리즘
이진 검색 알고리즘은 주어지 데이터가 오름차순으로 정렬되어 있다고 가정.
만약 실제 데이터가 정렬되어 있지 않다면, 우선 정렬 알고리즘을 이용해 정렬한 후에 이진 검색 알고리즘을 적용해야 함.
이진 검색 알고리즘은 영어로 Divide and Conquer(나누기 및 정복)이라고 표현하는데 의미 그대로 데이터를 나누고 검색하여 순차검색보다 효율을 높인다.
1,3,5,7,9의 배열 데이터가 있을 경우 이진 검색을 사용한다.
이때 중간 인덱스 값을 찾는 것이 핵심 로직!
중간 인덱스를 mid로 정의하고 low인덱스는 0, high 인덱스는 4로 본 후
각 회전 마다 중간 인덱스를 구하고 중간 인덱스의 값이 찾으려는 데이터인지를 비교한다.
(mid 값 보다 높으면 high인덱스 방향으로, 낮으면 low 인덱스 방향으로..)
1회전 :
A. 1회전 들어가기 전 : low = 0, high = 4, mid = (low+high)/2 = (0+4)/2 = 2
B. 1회전 : mid 값인 2 인덱스의 데이터인 5와, 찾으려는(target) 9를 비교한다.
데이터가 5보다 크므로 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해 low값을 mid+1로 증가해 low를 3으로 재설정한다.
2회전 :
A. 2회전 들어가기 전 : low = 3, high = 4, mid = (3+4)/2 = 3
B. 2회전 : mid값인 3 인덱스의 데이터인 7과 찾으려는 9를 비교한다.
데이터가 7보다 크므로 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해 low값을 mid+1로 증가해 low를 4로 재설정
3회전 :
A. 3회전 들어가기 전 : low = 4, high = 4, mid = (4+4)/2 = 4
B. 3회전 : mid값인 4 인덱스의 데이터인 9와 찾으려는 9를 비교한다. 3번의 검색 끝에 찾고자 하는 데이터를 구한다.
1.2 이진 검색 알고리즘 예제
문제 : 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾을 경우 비교하는 횟수는?
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15"
가. 2번 / 나. 3번 / 다. 4번 / 라. 5번
정답은 : 나. (3번)
해설 :
- 1회전 : (0 + 14) / 2 = 7번 째 인덱스의 값 : 8
- 2회전 : (8 + 14) / 2 = 11번 째 인덱스의 값 : 12
- 3회전 : (12 + 14) / 2 = 13번 째 인덱스의 값 : 14 <- 찾으려는 값.