[Algorithm] 이분탐색에서 Left Right 비교를 통해 값의 위치 찾기

이분 탐색에서 index를 이동할 때 좌우를 어떻게 비교하면서 이동하는지 확인해보자.


환경 및 선수조건

  • C++


원리

  1. 찾고자 하는 값을 x라 하고 배열을 a라 하자.
  2. 배열의 제일 왼쪽 인덱스를 Left 제일 오른쪽 인덱스를 Right라고 하자.
  3. Middle = (Left) + (Right - Left)/2라고 하자.
  4. left <= right를 만족하면 아래를 반복한다.
  5. x > a[Middle] 이면 Left = Middle + 1를 하고 그게 아니면 Right = Middle - 1를 한다.
  6. 다시 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);

}


참고자료

  • 코드플러스 알고리즘 중급 강의

[Python] pdb를 이용해 파이썬 코드 디버깅하기

> pdb를 이용해 python 코드를 디버깅하는 방법을 알아보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Python## pdb### pdb란?- ```pdb``` : 파이썬 디버깅 도구로 파인썬 인터프리터...… Continue reading