[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)

이진탐색이란?

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 핵심

 

동작방식

이진탐색 알고리즘은 리스트의 중간 값과 비교하여 검색 값을 찾습니다.

중간값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다.

 

동작 방식으로는 다음과 같습니다.

1. 배열의 중간 값을 가져옵니다.

2. 중간 값과 검색 값을 비교합니다.

     1) 중간 값이 검색 값과 같다면 종료합니다 (mid = key)

     2) 중간 값보다 검색 값이 크다면 기준 배열의 오른쪽 구간을 대상으로 탐색 합니다 (mid < key) 

     3) 중간 값보다 검색 값이 작다면 중간 값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key)

3. 값을 찾거나 간격이 비어있을 때까지 반복합니다.

 

 

시간 복잡도

시간 복잡도 O(logN) 입니다. 

1~n까지 탐색하는 것은 O(N)으로 이진 탐색이 훨씬 빠른 결과값을 찾을 수 있습니다.

 

 

<참고>

https://yoongrammer.tistory.com/75