2진 탐색 구현 (BinarySearch)

2진 탐색의 개념

• 문제를 반으로 계속 나누는게 핵심이다.
• 업 엔 다운을 반복적으로 하는것과 같음

2진 탐색 구현

첫째 값, 끝값, 찾을 값 지정

int search = 3;

// arr는 임의의 배열
int preIndex = 0;
int postIndex = arr.length-1;

반복의 구현, 중앙값 선언

• 반복의 조건은 preIndex 와 postIndex의 값이 같거나 작을때 이다.

int search = 3;

int preIndex = 0;
int postIndex = arr.length-1;

while (preIndex <= postIndex) {
	int mid = (preIndex + postIndex) / 2;
}

조건 구현

• 중앙값인 mid 선언
• 1번 2번의 값 조정의 이유는 범위를 좁히기 위함이다.

int search = 3;

int preIndex = 0;
int postIndex = arr.length-1;

while (preIndex <= postIndex) {
	
  	int mid = (preIndex + postIndex) / 2;
  
	// 1
	if (arr[mid] < search) {
    	preIndex = mid + 1;
    }
	
  	// 2
  	else if (search < arr[mid] {
        postIndex = mid - 1;
    }
    
    // 3
    else 
	    System.out.print();
		break;    	 
}