[알고리즘] 이분탐색

이진(이분) 탐색(Binary Search)이란

- 정렬되어있는 배열에서 데이터를 찾으려고 할 때 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법이다.

- '정렬되어있는 배열'이 필수 조건! 구현할 때 배열을 정렬시키는게 먼저 이루어져야한다.

- 시작과 끝, 그리고 그 중간을 나타내는 변수를 사용하여 탐색한다.
   left, right, mid 내지는 start, end, mid를 사용하는 듯 하다!

 

탐색 과정

이진 탐색과 순차 검색의 데이터 탐색 과정 차이

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

 

구현 과정은

1️⃣ 우선 데이터를 정렬한다(필수!!)

2️⃣ 시작값(start)과 끝값(end)으로 중간값(mid)을 구한다.

3️⃣ 이 mid와 구할 값을 비교한다.
    ☑️ 구할 값 > mid이면 left = mid + 1이고

    ☑️ 구할 값 < mid이면 right = mid - 1이다.

4️⃣ left > right이 될 때까지 반복!

 

 

📍 참고

https://velog.io/@kimdukbae/이분-탐색-이진-탐색-Binary-Search

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

 

https://wootool.tistory.com/62

[알고리즘] 이분 탐색