[JAVA] 이진탐색 ( Binary Search )

💡 이진 탐색 = 이분 탐색 ( Binary Search )

정렬된 배열 또는 리스트에 적합한 고속 탐색 방법

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.
• 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄인다.
• 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이진탐색이다.

 

 

💡 이진 탐색의 구현

 

1. 탐색의 대상이 되는 자료들이 array[low] 에서부터 array[high]에 들어있다. ( 정렬되어있어야함 )

  즉, 어떤 시점에서 탐색되어야 할 범위는 low~high까지가 된다.

  맨 처음 low에는 0번 index의 값, high에는 n-1번 index의 값이 들어갈 것이다.

 

2. low와 high 값에 의거해 중간값 mid 값은 (low+high)/2 이다.

 

3. array[mid] 값과 구하고자 하는 key 값을 비교한다.

• key > mid : 구하고자 하는 값이 중간값보다 높다면 low를 mid+1로 ( 왼쪽 반을 버림 )
• key < mid : 구하고자 하는 값이 중간값보다 낮다면 high를 mid-1로 ( 오른쪽 반을 버림 )
• key == mid : 구하고자 하는 값을 찾으면, mid값 return

4. low > high가 될 때까지 1~3번을 반복하면서 구하고자 하는 값을 검색

  

 

 

 

 

코드 구현

// 개인적인 변수명으로 low/high -> lt/rt로 사용
// 5개의 정수가 담긴 배열arr 있다고 가정
// arr는 정렬된 상태 ( sort(arr) )
int lt=0, rt=n-1;
while(lt<=rt){
	int mid=(rt+lt)/2;
    if(arr[mid]==key){
    	return mid; // 반환
    }else if(key<arr[mid]){
    	rt=mid-1; // 오른쪽 반을 버림
    }else{
    	lt=mid+1; // 왼쪽 반을 버림
    }
    return -1; // 탐색 실패
}