이분탐색

이분탐색은 크게 존재여부를 파악하는 알고리즘, lower bound와 upper bound를 찾는 알고리즘 두 가지가 있다.

 

존재여부를 파악하는 경우 = 중복원소를 고려하지 않음

lower bound와 upper bound = 중복원소를 고려

---

존재여부 파악 (중복원소 고려하지 않음)

public static int binarySearch(int[] arr, int key) {
 
	int lo = 0;					// 탐색 범위의 왼쪽 끝 인덱스
	int hi = arr.length - 1;	// 탐색 범위의 오른쪽 끝 인덱스
 
	while(lo <= hi) {
 
		int mid = (lo + hi) / 2;
 		
        if(key==arr[mid]){
        	return mid;
        }
		
		if(key < arr[mid]) {
			hi = mid - 1;
		}
		
		else if(key > arr[mid]) {
			lo = mid + 1;
		}
		
	}
}

 

중복원소 고려

lower bound

private static int lowerBound(int[] arr, int key) {
	int lo = 0; 
	int hi = arr.length; 
 
	// lo가 hi랑 같아질 때 까지 반복
	while (lo < hi) {
 
		int mid = (lo + hi) / 2; // 중간위치를 구한다.
 
		/*
		 *  key 값이 중간 위치의 값보다 작거나 같을 경우
		 *  
		 *  (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
		 */
		if (key <= arr[mid]) {
			hi = mid;
		}
 
		else {
			lo = mid + 1;
		}
 
	}
	return lo;
}

upper bound

rivate static int upperBound(int[] arr, int key) {
	int lo = 0; 
	int hi = arr.length; 
 
	// lo가 hi랑 같아질 때 까지 반복
	while (lo < hi) {
 
		int mid = (lo + hi) / 2; // 중간위치를 구한다.
 
		// key값이 중간 위치의 값보다 작을 경우
		if (key < arr[mid]) {
			hi = mid;
		}
		// 중복원소의 경우 else에서 처리된다.
		else {
			lo = mid + 1;
		}
	}
	return lo-1;
}

 

이때 주의할 점이 upper bound가 끝나서 리턴하는 값은 중복원소 다음의 인덱스를 가리킨다.

따라서 lo-1값을 return 함

 

 

 

 

참고 :

https://st-lab.tistory.com/261

https://st-lab.tistory.com/267

https://st-lab.tistory.com/277