[Algorithm] 이분탐색에서 Left Right 비교를 통해 값의 위치 찾기
이분 탐색에서 index를 이동할 때 좌우를 어떻게 비교하면서 이동하는지 확인해보자.
환경 및 선수조건
- C++
원리
- 찾고자 하는 값을
x라 하고 배열을a라 하자. - 배열의 제일 왼쪽 인덱스를
Left제일 오른쪽 인덱스를Right라고 하자. Middle = (Left) + (Right - Left)/2라고 하자.left <= right를 만족하면 아래를 반복한다.x > a[Middle]이면Left = Middle + 1를 하고 그게 아니면Right = Middle - 1를 한다.- 다시 3으로 돌아간다.
기본 코드
- 코드
while(left <= right){
int middle = left + (right - left)/2;
if(a[middle] == x){
// 배열에서 찾고자 하는 x의 위치가 position에 저장
positoin = middle;
break;
}
else if(a[middle] > x){
right = middle - 1;
}
else{
left = middle + 1;
}
}
예제 코드
- 코드
#include <stdio.h>
int main (){
// 정렬이 되어있어야함
int a[20] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int left = 0; // 제일 왼쪽 인덱스
int right = sizeof(a)/sizeof(int); // 제일 오른쪽 인덱스
int x = 3; // 값 3이 배열에서 위치한 인덱스를 찾고자 한다면
int position = -1;
while(left <= right){
int middle = left + (right - left)/2;
if(a[middle] == x){
// 배열에서 찾고자 하는 x의 위치가 position에 저장
position = middle;
break;
}
else if(a[middle] > x){
right = middle - 1;
}
else{
left = middle + 1;
}
}
printf("%d\n", position);
}