이진 탐색 ( Binary Search )
( 본 게시글은 작성자가 메모용으로 사용하는 용도임을 밝힙니다. 정보가 불확실할 수 있으니 참고 부탁드립니다 )
이진 탐색 ( Binary Search )은 정렬된 데이터의 리스트에서 원하는 값을 찾기 위해 탐색 범위를 점차 좁혀 나가면서, 값을 찾는 알고리즘이다. 이진 탐색은 데이터가 정렬되어야만 빠른 탐색 속도 효과를 기대할 수 있지만, 데이터가 정렬만 되어있다면, 빠르게 효율적으로 원하는 값을 찾을 수 있다는 장점이 있다.
이진 탐색의 동작 원리는 정렬된 데이터의 중간값과 값을 비교하여 검색 범위를 좁혀 나가는 방식이다. 리스트의 중간 값과 원하는 값을 비교하여, 만약 중간값과 원하는 값이 같다면, 원하는 값을 찾았으므로, 바로 함수가 종료된다. 그렇지 않을 경우는 2가지로 나뉘는데, 만약 원하는 값이 중간값보다 크다면, 원하는 값은 현재 중간값과 리스트의 가장 끝값 사이에 있기 때문에, 그 이외의 범위는 검색 범위에서 제외할 수 있다. 0 ~ 100까지의 101개의 정수가 있다면 중간값은 50이다. 여기서 만약 77을 찾고싶다면 50과 77을 비교한다. 검색값인 77인 중간값인 50보다 크기 때문에 검색 범위를 50부터 100까지만 보고, 그 이하의 범위는 생각하지 않아도 된다. 그다음 51 ~ 100의 범위에서의 다시 중간값을 도출하고, 중간값인 75와 77을 비교하여 보면 이번에도 검색값이 더 크기때문에 76과 100의 범위로 좁혀진다. 이렇게 범위를 좁혀나가면서 원하는 값을 찾아 내는 방식이다.
이진 탐색의 탐색 조건으로는 최솟값이 최댓값 보다 작을때만 실행되어야하고, 만약 최솟값이 최댓값보다 클 경우는 검색할 범위가 없음으로 간주하여 탐색이 종료된다. 또한 중간값과 검색값의 대소에 따라 왼쪽값과 오른쪽값의 변경은 중간값이 아닌 중간값에서 1을 더하거나 1을 뺀 값으로 변경된다.
이진 탐색을 구현하기 위해, 데이터값이 들어가 있는 Data.txt 텍스트파일을 사용한다. 해당 텍스트 파일에는 unsigned short형 만큼의 크기 0 ~ 65534만큼 데이터가 들어가있고, 각 인덱스마다 랜덤한 정수가 저장되어있다. 때문에, 데이터를 저장할 구조체 Data에 값의 Index가 들어갈 변수 Index와, 실제 데이터값을 저장할 Score 변수를 선언한다. 그리고 텍스트 파일을 읽어올 ReadData 함수를 정의해준다. 함수 내에는 fopen_s로 Data.txt 텍스트 파일을 읽기모드로 열고, 텍스트파일을 넣어줄 구조체를 참조하는 포인터 file을 넣어준다. 다음 fscanf로 참조하는 데이터에 Index와 Score로 값을 스캔해준다.
다음 SequenceSearch는 순차탐색으로 데이터값을 순차적으로 탐색하는 과정으로 n번째 index 값을 탐색하려면 n번만큼 탐색을 진행해야한다.
이진 탐색은 BinarySearch는 최솟값이 될 left를 0으로, 최댓값이 될 right를 크기에서 -1 한 값으로 초기화해줘 초기 탐색 범위를 지정해준다. 다음 while문으로 최솟값이 최댓값보다 작거나 같을때의 조건을 설정하여, 최솟값 최댓값의 합을 2로 나눈값을 중간값으로 설정하고, 다음 if문의 분기로 탐색을 진행한다.
위에 설명한대로 중간값의 데이터와 검색값인 매개변수 target이 같다면 그대로 중간값의 데이터를 리턴하고, 검색값이 더 크다면, 최솟값에 중간값에 1을 더하여 범위를 좁히고, 검색값이 더 작다면, 최댓값에 중간값에 1을 빼서 범위를 좁힌다.
main 함수에서 unsigned short의 가장 큰값 65534만큼의 datas 배열을 선언한다.
그리고 탐색횟수 변수 count와, 검색값 target을 선언하고, 원하는 탐색값을 21454로 설정한다. 참고로 21454의 index는 55032이다.
다음 순차탐색으로 datas에서 target을 찾고, 이진탐색으로도 datas에서 target을 찾아본다.
순차탐색으로는 index인 55032번만에 찾았고, 이진 탐색으로는 16번만에 찾은 것을 확인할 수 있다.
이진 탐색을 사용하면 정렬된 데이터에 한정하여, 기존 탐색법보다 훨씬 효과적으로 값을 찾을 수 있다.