Binary Search 이진 탐색

Binary Search란 

< 그림으로 설명 >

[이진 탐색] 

left, right: 배열(a[0], a[1], ⋯, a[n-1])의 왼쪽, 오른쪽 끝 지점

 초기 값으로 left = 0, right = n-1

 list의 중간 위치 middle = (left + right) / 2로 설정

a[middle]과 x를  비교할 경우 3가지 경우 중에 하나를 고려

⑴ x > a[middle]: left를 middle+1로 설정

⑵ x < a[middle]: right를 middle-1로 설정

⑶ x = a[middle]: middle을 반환

예시) C++

int BinarySearch (int *a, const int x, const int n){    // x - 찾으려는 값, n = 배열의 원소 수 or 찾으려는 배열의 크기

int left = 0, right = n -1;

// 찾거나 left가 right 넘어갈 경우 멈춘다.

while(left <= right){

int middle = (left + right) / 2;    //중간위치 항상 

if(x > a[middle]) left = middle + 1 ;

else if (x < a[middle]) right = middle - 1;

else return middle    //찾앗다.

}

//못 찾았다.

return -1;

}