반응형
1. Binary Search (이진탐색)
이미 정렬되어 있는 배열에서 원하는 값을 찾을 때 사용하는 탐색 방법이다. 탐색 대상이 되는 리스트의 중간값을 기준으로 반으로 나눠 반복적으로 탐색을 진행한다.
찾고자 하는 타겟값이 중간값보다 작은 경우에는 왼쪽 리스트를 중간값보다 큰 경우에는 오른쪽 리스트를 탐색 대상으로 반복 탐색을 진행한다. 만약 타겟값과 중간값이 일치하는 경우 해당 위치를 반환하면 된다. 만약에 반복을 계속해서 서브 리스트의 크기가 0일 때까지 반복한다.
2. Binary Search 구현
import java.util.Arrays;
import Algorithm.Search.Search;
public class BinarySearch implements Search {
private int N;
private int[] nums;
public BinarySearch(int[] nums) {
N = nums.length;
this.nums = Arrays.copyOf(nums, N);
}
@Override
public int search(int val) {
// 초기 배열의 탐색 대상 범위를 0 ~ N 으로 설정한다.
int left = 0, right = N;
// 탐색 대상 범위의 크기가 0이 될때까지 반복한다.
while(left < right) {
// 대상 범위의 중간값을 구한다.
int mid = (left + right) / 2;
// 중간값과 타겟값이 같은 경우 해당 값의 인덱스를 반환한다.
if(nums[mid] == val) {
return mid;
// 타겟값이 중간값보다 큰 경우 중간값의 오른쪽 부분 배열을 대상으로 탐색을 진행한다.
} else if(nums[mid] < val) {
left = mid + 1;
// 타겟값이 중간값보다 작은 경우 중간값의 왼쪽 부분 배열을 대상으로 탐색을 진행한다.
} else {
right = mid;
}
}
// 타겟값이 없는 경우 -1을 반환한다.
return -1;
}
}
- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Search/BinarySearch/BinarySearch.java
3. Binary Search 복잡도
- 시간 복잡도: O(log N)
- 탐색 대상의 범위가 계속해서 반으로 나눠지기 때문에 최종적으로 N개의 수에 1/2를 k 만큼 곱한 값이 1이 될 때까지 반복하게 된다.
- 이때 k의 값은 log N에 수렴하게 된다.
[reference]
- https://www.geeksforgeeks.org/binary-search/
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
[Algorithm] Bellman-Ford Algorithm (벨만 포드 알고리즘) (0) | 2021.09.27 |
---|---|
[Algorithm] Dijkstra's Algorithm (다익스트라 알고리즘) (0) | 2021.09.27 |
[Algorithm] Counting Sort (계수정렬) (0) | 2021.07.09 |
[Algorithm] Quick Sort (퀵정렬) (0) | 2021.07.07 |
[Algorithm] Heap sort (힙정렬) (0) | 2021.07.06 |