💡 해당 예시로 int[] arr = {1, 3, 5, 8, 11, 15, 30, 32, 45}이고 key 값이 8인 경우의 이진탐색을 찾는 원리를 확인합니다.
1. while문으로 구성하는 이진 탐색
💡 아래의 예시는 정렬된 배열 arr에서 key 값을 찾는 이진 탐색을 구현한 예시입니다.
1. low는 첫번째 인덱스, high는 마지막 인덱스를 지정합니다.
2. 마지막 인덱스 보다 첫번째 인덱스가 같아지거나 작을 경우까지 순회합니다.
3. 중간 값을 구합니다.
4.1. 중간 값보다 찾으려는 값(key)가 큰 경우 중간 값에 1을 더하여 오른쪽 절반을 탐색합니다.
4.2. 중간 값보다 찾으려는 값(key)가 작은 경우 중간 값에 1을 빼고 왼쪽 절반만 탐색합니다.
4.3. 이외에 경우 중간 값을 최종값으로 반환합니다.
5. 최종 탐색을 못한 경우 값은 -1로 반환합니다.
/**
* 이분탐색
*
* @param arr {int[]}: 전체 배열
* @param key {int}: 찾고자 하는 요소
* @return ResponseEntity<ApiResponse>
* @link
* @since 2023.05.
*/
@GetMapping("/1")
public ResponseEntity<ApiResponse<Object>> binSearchCourse(@RequestParam int[] arr, @RequestParam int key) {
int answer = 0;
// [STEP1] 시작 인덱스와 마지막 인덱스 값을 지정합니다.
int low = 0;
int high = arr.length - 1;
// [STEP2] 마지막 인덱스를 보다 첫번째 인덱스가 같아지거나 작을 경우까지 순회합니다.
while (low <= high) {
// [STEP3] 중간 값을 구합니다.
int mid = (low + high) / 2;
// [CASE4-1] 중간 값보다 찾으려는 값(key)가 큰 경우 : 중간 값에 1을 더하여 오른쪽 절반을 탐색합니다.
if (arr[mid] < key) {
low = mid + 1;
}
// [CASE4-2] 중간 값보다 찾으려는 값(key)가 작은 경우 : 중간값에 1을 빼서 왼쪽 절반을 탐색합니다.
else if (arr[mid] > key) {
high = mid - 1;
}
// [CASE4-3] 해당 경우가 아니면 중간값을 최종 값으로 반환합니다.
else {
answer = mid;
}
}
// [STEP5] 최종 탐색을 하지 못할 경우 -1을 반환합니다.
if (answer == 0) answer = -1;
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
2. 재귀함수를 이용한 이진 탐색
1. 높은 인덱스가 낮은 인덱스보다 크거나 같은지 확인합니다.
2. 중간 값을 구합니다.
3. 배열의 요소 값이 찾는 값과 동일하면 중간 값을 반환합니다.
4. 중간 값이 키보다 큰 경우 : 낮은 인덱스와 중간 인덱스에서 1을 뺀 값을 가지고 함수를 재귀적으로 호출합니다.
5. 중간 값이 키보다 작은 경우 : 중간 인덱스에 1을 더하고 높은 인덱스와 함께 함수를 재귀적으로 호출합니다
/**
* 재귀를 사용하여 이진 알고리즘을 구현합니다.
* @param arr 배열
* @param low 낮은 인덱스
* @param high 높은 인덱스
* @param key 검색할 값
* @return
*/
public static int binarySearch(int[] arr, int low, int high, int key) {
// 1. 높은 인덱스가 낮은 인덱스보다 크거나 같은지 확인합니다.
if (high >= low) {
// 2. 중간 값을 구합니다.
int mid = low + (high - low) / 2;
// 3. 배열의 요소 값이 찾는 값과 동일하면 중간 값을 반환합니다.
if (arr[mid] == key) {
return mid;
}
// 4. 중간 값이 키보다 큰 경우 : 낮은 인덱스와 중간 인덱스에서 1을 뺀 값을 가지고 함수를 재귀적으로 호출합니다.
else if (arr[mid] > key) {
return binarySearch(arr, low, mid - 1, key);
}
// 5. 중간 값이 키보다 작은 경우 : 중간 인덱스에 1을 더하고 높은 인덱스와 함께 함수를 재귀적으로 호출합니다
else {
return binarySearch(arr, mid + 1, high, key);
}
}
// 6. 높은 인덱스가 낮은 인덱스보다 작으면 배열에서 키를 찾지 못했음을 나타내기 위해 -1을 반환합니다.
return -1;
}
2) 이진 탐색의 문자열 탐색
💡 문자열 배열의 경우 이진/이분 탐색을 사용하는 경우 Arrays.binarySearch() 함수를 이용합니다.
1. Arrays.binarySearch()
💡 Arrays.binarySearch() 함수
- 매개변수로 주어진 배열에서 원하는 값을 이진 탐색하여 인덱스를 반환합니다. 만약 해당 원소가 배열에 없다면 음수를 반환합니다. 이진 탐색을 하기 전에 반드시 배열을 정렬해야 합니다.
public static int binarySearch(Object[] a, Object key)
Arrays.binarySearch() 메서드 파라미터 설명
타입
설명
Object[]
탐색하고자 하는 배열
Object
배열에서 찾으려는 값
2. Arrays.binarySearch()를 이용한 이진 탐색 예시
💡 해당 예시는 String[] 내에서 key 값을 찾고 있습니다. 💡 Arrays.binaraySearch() 함수를 이용하여 배열 내에 key 값이 존재하는지 확인합니다.
import java.util.Arrays;
/**
* 이분탐색 : 문자열
*
* @param arr {int[]}: 전체 배열
* @param key {int}: 찾고자 하는 요소
* @return ResponseEntity<ApiResponse>
* @link
* @since 2023.05.
*/
@GetMapping("/2")
public ResponseEntity<ApiResponse<Object>> binSearchCourse(@RequestParam String[] arr, @RequestParam String key) {
int answer = 0;
Arrays.sort(arr);
int result = Arrays.binarySearch(arr, key);
if (result < 0) {
System.out.println("Element is not present in the array.");
} else {
System.out.println("Element is present at index " + result);
}
ApiResponse<Object> ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
💡 [참고] 좀 더 다양한 알고리즘에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
