binary search2 [Algorithm] 이분 탐색 (Binary Search) 1. 탐색(Search)이란? 수열과 탐색 대상 X가 주어졌을 때, X가 존재하는 지? X[이하, 미만, 이상, 초과]의 원소는 몇 개가 있는지? X랑 가장 가까운 원소는 무엇인지? 모두 시간복잡도 O(N)을 가진다. 2. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 "이분"하면서 탐색하는 방법 1) 임의의 M번 인덱스에 있는 A[M]이 X보다 크다면, A[M...N]은 전부 X보다 크다. 2) 임의의 M번 인덱스에 있는 A[M]이 X보다 작다면, A[1...M]은 전부 X보다 작다. * 오름차순 정렬이기 때문에 생기는 성질! 정렬이 아니라면 불가능하다. (1) 이분탐색 과정 L := X를 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R := X를 탐색할 가치가.. 2022. 1. 24. [Algorithm] 이분 탐색 (Binary Search) 1. 탐색(Search)이란? 수열과 탐색 대상 X가 주어졌을 때, X가 존재하는 지? X[이하, 미만, 이상, 초과]의 원소는 몇 개가 있는지? X랑 가장 가까운 원소는 무엇인지? 모두 시간복잡도 O(N)을 가진다. 2. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 "이분"하면서 탐색하는 방법 1) 임의의 M번 인덱스에 있는 A[M]이 X보다 크다면, A[M...N]은 전부 X보다 크다. 2) 임의의 M번 인덱스에 있는 A[M]이 X보다 작다면, A[1...M]은 전부 X보다 작다. * 오름차순 정렬이기 때문에 생기는 성질! 정렬이 아니라면 불가능하다. (1) 이분탐색 과정 L := X를 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R := X를 탐색할 가치가.. 2022. 1. 24. 이전 1 다음 반응형
