이진 검색과 이진 검색 알고리즘에 대해 알아봅시다. (자바)

백준님의 문제를 해결하다가 이진 검색을 사용하게 된 문제가 생겨서 글을 씁니다.

먼저 이진 검색이 제공됩니다. 정렬된 목록에서 특정 값을 찾는 알고리즘입니다. 리스트를 반으로 나누어 검색 범위를 좁혀 원하는 값을 찾는 방식이다.

이 알고리즘은 매우 효율적으로 작동하며 검색 대상이 많은 대규모 데이터 세트에 유용합니다. 이진 검색의 시간 복잡도는 O(log N)입니다.

---

bipartite 검색 알고리즘은 다음과 같이 서면으로 설명됩니다.

1. 주어진 리스트의 처음 인덱스와 끝 인덱스를 처음에 받아 2로 나누어 중간값을 찾는다.

예) 중간 = (낮음 + 높음 ) / 2

2. 주어진 목록이 정렬되어 있으므로 목록 중간에 있는 요소와 찾고 있는 요소를 비교합니다.

이때 찾을 요소인 key의 값이 mid의 요소와 같으면 값을 찾은 것이다.

mid의 요소 값이 찾고자 하는 키 값보다 작은 경우 현재 키 값이 mid의 큰 쪽에 있으므로 더 큰 절반에 대해 이분 검색을 다시 수행합니다.

반대로 mid의 요소 값이 검색할 키 값보다 크면 현재 키 값이 mid의 작은 쪽에 있으므로 더 작은 절반에 대해 다시 이분 검색을 수행합니다.

삼. 이를 mid의 요소 값과 key 값이 같을 때까지 반복하다가 조회하고자 하는 요소 값이 리스트에 존재하지 않고 더 이상의 조회 범위가 없으면 조회할 값이 없기 때문에 리스트를 종료한다. 주어진 목록에서 검색됩니다.

그림을 보시면 이해가 더 쉬우실 거에요.

---

Java 코드를 통한 이진 검색의 예입니다.

코드를 보면 arr(mid)를 기준으로 키값과의 비교를 통해 범위가 좁혀진다.