[알고리즘] 이진 탐색

✔ 검색

• 검색(Search) : 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업

✅ 검색의 종류

• 순차 검색
• 이진 검색
• 해쉬

✔ 이진 검색(Binary Search)

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

• 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
• ⭐ 자료가 정렬된 상태여야함
• 시간복잡도 O(logN)

✅ 검색 과정

• 자료의 중앙에 있는 원소를 고른다.
• 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
• 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
• 찾고자 하는 값을 찾을 때까지 위의 과정 반복.

✅ 참조 : 이진검색을 사용한 코드

https://velog.io/@jiwoni1/%EB%B0%B1%EC%A4%80-10815-%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89