국어 사전과 이진 탐색의 공통점

이진 탐색은 무엇인가 이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 그래서 이거 왜 쓰는데? 국어 사전을 살펴본다고 가정하자. (지금은 잘 쓰지 않지만) "사랑"이라는 단어를 찾아본다고 할 때, 우선 "ㅅ"에 해당하는 파트로 이동해야한다. 그리고 우연히 찾은 페이지가 "소나무"(사전순으로 봤을 때에 사랑보다 뒤에 위치한다)라면 그보다 앞으로 더 이동해서 "사랑"을 찾아야한다. 이런식으로 내가 원하는 단어와 현재 단어의 순서를 비교하며 찾아간다는 점이 유사하다고 할 수 있다. 뿐만 아니라, 해당 방식은 처음부터 원하는 단어까지 순차적으로 탐색을 하는 방식보다 시간이 매우 단축될 것이다. 이진 탐색을 사용할 수 있는 조건 앞서 예시를 둔 국어 사전은 기본적으로 사전순으로 정렬이 되어있다 따라서, 현재 단어의 위치를 파악하여 앞으로 갈지 뒤로 갈지를 판단할 수 있다. 이진 탐색도 마찬가지이다. 현재 데이터의 위치를 파악하여 앞으로 갈지 뒤로 갈지를 판단해야하기 때문에 정렬된 리스트에서만 사용할 수 있다. 동작원리와 예시 코드 1. 탐색할 배열을 정렬한다. 2. 배열의 중간 인덱스 값을 기준으로 탐색을 시작한다. 3. 중간 값과 찾고자 하는 값을 비교한다.    3-1. 중간 값이 찾고자 하는 값보다 작으면 왼쪽 부분 배열을 탐색한다.    3-2. 중간 값이 찾고자 하는 값보다 크면 오른쪽 부분 배열을 탐색한다. 4. 찾고자 하는 값이 중간 값과 일치하면 해당 위치를 반환하고, 아니면 반복하여 탐색을 진행한다. 5. 탐색할 부분 배열의 크기가 0이 될 때까지 위의 과정을 반복한다. def binary_search(arr, target): left = 0 right = len(arr)-1 while left <= right: mid = (left+right)//2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid+1 else: right = mid-1 return -1 # 찾지 못한 경우 블로그 : https://justgotothedesk.tistory.com/152 예시 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/64062