[Java] 이진 탐색(Binary Search)

프로그래머스의 문제를 풀다가 새롭게 알게된 이진 탐색에 대해 정리하였다.

이진 탐색(Binary Search)이란?

👉 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘

👉 대상 데이터의 중앙값과 찾고 싶은 대상을 비교하여 데이터의 크기를 절반씩 줄여가며 대상을 찾음

👉 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 알고리즘

 

 

이진 탐색의 시간복잡도

👉 O(logN)

 

 

이진 탐색 알고리즘 탐색 과정

해당 알고리즘은 반드시 정렬된 상태에서 진행하여야 함

1️⃣ 현재 데이터 셋의 중앙값(mid) 선택

2️⃣ 중앙값 > 찾고 싶은 대상 값이라면 중앙값 기준으로 왼쪽 데이터셋 선택

3️⃣ 중앙값 < 찾고 싶은 대상이라면 중앙값 기준으로 오른쪽 데이터셋 선택

4️⃣ 중앙값 == 찾고 싶은 대상일때까지 1️⃣~3️⃣의 과정을 반복

만약, 오름차순으로 정렬되어 있다면 위의 1️⃣~4️⃣의 과정을 그대로 하면 되고,

내림차순으로 정렬되어 있다면 조건을 반대로 하여 과정을 반복하면 됨