[알고리즘] 이분 탐색 / 이진 탐색 Java

이분 탐색  /  이진 탐색

 

- 데이터가 정렬돼 있는 상태에서 값을 찾아내는 알고리즘 이다
- 데이터의 중앙값과 찾고 하는 값을 비교해서 데이터의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다
- 데이터가 정렬되어 있어야만 사용할 수 있다

 

기능	특징	시간 복잡도
타깃 데이터 탐색	중앙값 비교를 통한 대상 탐색 축소 방식	O(logN)

 

 

탐색 과정

1) 현재 데이터셋의 중앙값을 선택한다 
2) 중앙값 > 타깃 데이터 일때 중앙값 기준으로 왼쪽 데이터셋을 선택한다
3) 중앙값 < 타깃 데이터 일때 중앙값 기분으로 오른쪽 데이터셋을 선택한다
4) 과정 1~3 을 반복하여 중앙값 == 타깃 데이터일때 탐색을 종료한다

 

 

Java로 하는 이분 탐색 구현 

 

1. 반복문 구현

public boolean searchBinary (int[] array, int n) {
		int left = 0;
		int right = array.length - 1;
		int mid = 0;

		while (left <= right) {
			mid = (left + right) / 2;
			if (array[mid] < n) {
				left = mid + 1;
			} 
			else if (array[mid] > n) {
				right = mid - 1;
			}
			else {
				return true;
			}
		}
		return false;
	}

 

 

2. 재귀로 구현

public boolean binarySearchRecursive(int[] array, int n, int left, int right) {
		if(left > right) {
			return false;
		} 
		
		int mid = (left + right) / 2;
        
		if (array[mid] < n) {
        	return binarySearchRecursive(array, n, mid +1, right);
		}
		else if (array[mid] > n) {
			return binarySearchRecursive(array, n, left, mid - 1);
		}
        	
		else {
        	return true;
		}
	}

 

---

Upper bound & Lower bound 

 

- 경곗값을 찾는 알고리즘이다
- 이진 탐색을 기반으로 하는 알고리즘이다 (그래서 정렬이 되어 있어야 함)

 

 

Upper bound

 

- 특정 k값보다 처음으로 큰 값의 위치를 찾는 알고리즘 
- 배열에서 특정 값 x를 초과하는 값이 처음으로 나타나는 위치 (index 값)

 

 

Upper bound 동작 방식 

 

초기에 left와 right는 동일하게 시작과 배열의 끝으로 세팅한다

1. mid 값을 가져온다 -> (left + right) / 2 
2. 중간 값과 검색 값을 비교하여 
- 중간 값 <= 검색 값  일때 left = mid + 1 로 세팅
- 중간 값 > 검색 값 일때 right = mid
3. left >= right 가 될때 까지 1번과 2번을 반복한다
4. 반복이 끝나면 right 값이 upper bound 가 된다

 

구현

public int searchBinaryUpperBound(int[] array, int target) {
		int left = 0;
		int right = array.length - 1;
		int mid = 0;

		while (left <= right) {
			mid = (left + right) / 2;
			if (array[mid] <= target) {
				left = mid + 1;
			} 
			else {
				right = mid - 1;
			}

		}
		return right;
	}

 

 

 

Lower bound

- 특정 값의 시작 위치를 찾는 알고리즘 이다
- 배열에서 x 이상의 값이 처음으로 나타나는 위치 (index 값)

 

 

동작 방식

 

초기에 left와 right는 동일하게 시작과 배열의 끝으로 세팅한다

1. mid 값을 가져온다 -> (left + right) / 2 
2. 중간 값과 검색 값을 비교하여
- 중간 값 < 검색 값 일때 left = mid +1 로 세팅
- 중갑 값 >= 검색 값 일때 right = mid 로 세팅
3. left >= right 가 될때 까지 1번과 2번을 반복한다
4. 반복이 끝나면 right 값이 Lower bound 가 된다

 

 

구현

public int searchBinaryLowerBound(int[] array, int target) {
		int left = 0;
		int right = array.length - 1;
		int mid = 0;

		while (left < right) {
			mid = (left + right) / 2;
			if (array[mid] >= target) {
				right = mid - 1;
			} 
			else {
				left = mid + 1;
			}

		}
		return left;
	}

 

---

이분 탐색에 해당하는 코딩 테스트 문제들 list

- 난이도는 순서대로 높아집니다 

 

1. https://hyeonni.tistory.com/11

[백준] 2512 예산 - Java

 

2. https://hyeonni.tistory.com/12

[백준] 19637 IF문 좀 대신 써줘 - Java

 

3. https://hyeonni.tistory.com/13

[백준] 2805 나무 자르기 - Java

 

4. https://hyeonni.tistory.com/14

[백준] 1654 랜선 자르기 -Java

 

5. https://hyeonni.tistory.com/19

[백준] 2470 두 용액 - Java