[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);

}


참고자료

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

[Docker] 도커(Docker) 이미지 이름과 태그 목록 가져오기

> 도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Docker- awk, tail 명령어## 도커(Docker...… Continue reading