오늘 배운 알고리즘은
01. 이진탐색(binary search)
"정렬된 배열" 에서 내가 원하는 것 찾기!
매 단계에서 중간값을 찾아가는게 핵심
시간복잡도가 O(logn) 반 탐색하고 반 탐색하고 하는 로직이라 탐색범위가 반으로 줄어든다
오늘 푼 예제는 한쪽으로만 탐색하는 파라매트릭 탐색을 했는데, 이진탐색의 기초는 양쪽을 탐색하는 것이 중요하다고 봅니다.
package src.com.company.week2.day3;
public class BinarySearchExample {
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = r - l / 2;
// 중간값이 찾는 값과 같은 경우
if (arr[mid] == x)
return mid;
// 중간값이 찾는 값보다 큰 경우 왼쪽 탐색
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// 중간값이 찾는 값보다 작은 경우 오른쪽 탐색
return binarySearch(arr, mid + 1, r, x);
}
// 찾는 값이 배열에 없는 경우
return -1;
}
public static void main(String[] args) {
BinarySearchExample ob = new BinarySearchExample();
int arr[] = {2, 3, 4, 10, 40};
int n = arr.length;
int x = 10; // 찾고자 하는 값
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println( x + "를 찾을 수 없습니다.");
else
System.out.println( x + "가 발견된 인덱스: " + result);
//10가 별견된 인덱스: 3
}
}
// 추가 작성하기
코드 요약을 하면 arr[] 배열 안에 2,3,4,10,40이라는 정렬! 되어있는 원소가 주어지는데, 그 중 10을 찾는 코드다.
int binarySearch(int arr[], int l, int r, int x) 는 실질적으로 이분탐색을 하는 코드인데,
탐색할 정렬된 배열, 왼쪽은 0(인덱스 시작값), 오른쪽은(인덱스 가장 큰 값), 찾을 값을 파라미터로 넣어줍니다.
그 후 중간값을 찾을 것이다.
나는 인덱스로 찾을 것이기 때문에 (0번인덱스 + 5번인덱스) / 2 를 해 줍니다. 그럼 3이 나