[2021/07/26][짤막한 이야기 - 이진 탐색]

[2021/07/26][짤막한 이야기 - 이진 탐색]
“이진 탐색(Binary Search)”이란 어떠한 그룹을 탐색할 때 절반으로 나누어가며 탐색하는 기법이다.
일반적으로 정렬이 적용된 자료구조에서 특정한 값을 탐색할 때에 적용하는 탐색 방법을 의미한다.
“정렬”은 알고리즘에서도 매우 중요한 개념 중 하나로 다음에 소개할 주제이기도 하다.
예를 들어, 1 ~ 100,000까지의 공간에서 특정한 수(X)를 탐색할 때 중간에 해당하는 인덱스인 50,000번째부터 확인하게 된다.
50,000번째 공간에 저장된 수(Y)가 찾고자 하는 특정한 수와 같다(X = Y)면 정말 행운이지만, 일반적으로는 그렇지 않다.
만약 특정한 수보다 저장된 수가 작은 경우(X > Y)라면 그 공간의 오른쪽을, 반대(X < Y)라면 그 공간의 왼쪽을 탐색하면 된다.
이 경우에도 오른쪽 절반 혹은 왼쪽 절반에 해당하는 인덱스(75,000 or 25,000)를 선택하면 된다.
이 방법의 장점은 공간이 정렬되어 있을 때, N개의 공간 내에서 특정한 수 X를 찾기 위한 시간이 logN의 복잡도를 가지기 때문에, 순차적으로 탐색하는 경우(순차 탐색은 N의 복잡도를 가짐)에 비하여 매우 빠르다는 점이다.
성인 독자들의 경우, “업앤다운(Up & Down)”이라는 게임을 생각하면 이해하기 편할 것이다.
#이야기 #루니프 #알고리즘 #이진탐색 #정렬 #시간복잡도 #업앤다운

[2021/07/26][Short Story - Binary Search]
“Binary Search” is a method of searching in half when searching a group.
In general, it refers to a search method applied when searching for a specific value in a data structure to which sorting is applied.
“Sorting” is one of the most important concepts in algorithms, which will be introduced next.
For example, when searching for a specific number (X) in the space from 1 to 100,000, the index corresponding to the middle, 50,000, is checked.
You're really lucky if the number (Y) stored in the 50,000th space equals the specific number you're looking for (X = Y), but that's usually not the case.
If the stored number is smaller than a specific number (X > Y), search the right side of the space, and vice versa (X < Y), search the left side of the space.
In this case, as well, you can select the index (75,000 or 25,000) corresponding to the right half or the left half.
The advantage of this method is that when space is sorted, the time to find a specific number X in N spaces has a complexity of logN, so it is very fast compared to the sequential search (sequential search has a complexity of N).
Adult readers will find it easier to understand by thinking of a game called “Up & Down.”
#Story #LooNiP #Algorithm #BinarySearch #Sort #TimeComplexity #UpDown