목록2023/04/15 (1)

HJW's IT Blog

Algorithm: Binary Search

Binary Search 란 정렬된 배열에서 원하는 값을 빠르게 찾기 위한 알고리즘이다 Binary Search는 반으로 나누어 검색하는 방법으로 시간 복잡도는 O(log n) 이다. 동작과정 1. 배열의 중간값을 선택한다 2. 중간값과 찾고자 하는 값을 비교 --> 중간값이 찾고자 하는 값과 같으면 검색을 종료 --> 찾고자 하는 값이 중간값보다 작으면 배열의 왼쪽으로 다시검색 --> 찾고자 하는 값이 중간값보다 크다면 배열의 오른쪽으로 다시 검색 --> 위 방법 반복 경비실 문제 무식한 방법 M이 가장 왼쪽에 있는 집부터 가장 오른쪽에 있는 집까지의 거리. 모든 (M,k) 에 대해 다 조합해본다: O(M^k) 시간 착안점 --> 경비실이 k개 있다면 집에서 경비실 까지의 거리는 M/(2k) 보다 멀 ..
알고리즘 2023. 4. 15. 16:42
이전 Prev 1 Next 다음