이분 탐색

✍️  정의

이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복잡도가 순차적 탐색보다 낮다.

---

🆚  순차적 탐색 vs 이분 탐색

순차적 탐색

• 정렬된 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 차례로 탐색

이분 탐색

• 정렬된 배열 안에서 특정 원소를 찾을 때, 인덱스 left와 right의 중간값과 비교
• 중간값과 비교해서 찾는 원소가 아니면 인덱스 left 또는 right를 다시 정해준다.
• 인덱스 left와 right를 정할 때마다 탐색 범위는 반으로 줄어든다.

---

🔎  이분 탐색 방법

1. 처음 범위는 인덱스 left = 0, right = 끝, mid = (left + right) / 2
2. mid의 값과 찾는 원소를 비교한다.
   1. mid == 찾는 원소이면, 탐색 종료
   2. mid < 찾는 원소이면, left = mid + 1 로 하여 다시 반복
   3. mid > 찾는 원소이면, right = mid - 1 로 하여 다시 반복
3. 만약 left > right 가 된다면, 해당 배열에는 찾는 원소가 없다.

---

⏰ 시간 복잡도

순차적 탐색 ( O(n) )

• 최악의 경우, 배열의 끝까지 탐색해야 한다.

이분 탐색 ( O(log n) )

• 범위를 새로 정할 때마다 탐색 범위는 1/2씩 줄어든다.

 

인용

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

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