-
[알고리즘] 이분 탐색 / 이진 탐색 Java알고리즘 2024. 4. 22. 19:22
이분 탐색 / 이진 탐색
- 데이터가 정렬돼 있는 상태에서 값을 찾아내는 알고리즘 이다
- 데이터의 중앙값과 찾고 하는 값을 비교해서 데이터의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다
- 데이터가 정렬되어 있어야만 사용할 수 있다기능 특징 시간 복잡도 타깃 데이터 탐색 중앙값 비교를 통한 대상 탐색 축소 방식 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
- 난이도는 순서대로 높아집니다
2. https://hyeonni.tistory.com/12
3. https://hyeonni.tistory.com/13
4. https://hyeonni.tistory.com/14
5. https://hyeonni.tistory.com/19
'알고리즘' 카테고리의 다른 글
[알고리즘] Two-Pointers Algorithm (투 포인터 알고리즘) (1) 2024.06.15