[알고리즘] 이분 탐색

 

 

이진 검색 알고리즘이라고도 한다

이분 탐색은 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘이다.

 

특정 값의 위칠를 찾는 방법은

 

1. 배열에서 중간 위치를 찾아서

2. 해당 값보다 크다면

3. 탐색 범위를 다시 중간값+1 부터 시작해서 끝까지 재 탐색하는 것이다.

 

 

중간 값 = (시작 위치 + 끝나는 위치) / 2

 

* 원하는 값이 중간 값보다 크다면 중간값 다음 자리인 7을 시작위치로 다시 설정해서(배열 위치로는 4번째) 중간값을 다시 찾아서 탐색한다.

 

* 원하는 값이 중간 값보다 작다면 중간값 앞의 자리인 3을 끝나는위치로 다시 설정해서(배열 위치로는 2번째) 중간값을 다시 찾아서 탐색한다.

 

* 이 과정을 원하는 값이 중간 값으로 나올때까지 찾는다.

 

c++ 코드

//left는 시작 위치 rifht는 끝나는 위치 N은 배열의 갯수
int left = 0, right = N - 1;
 
//num은 찾고자 하는 숫자 arr은 저장된 배열
while (left <= right) {
    mid = (left + right) / 2;        //중간값 계산
    if (arr[mid] > num) {
        right = mid - 1;
    }
    else if (arr[mid] < num) {
        left = mid + 1;
    }
    else {
        //탐색 완료
        break;
    }
}