[알고리즘] 이진 검색

퀴즈

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem

퀴즈풀이

• 단순하게 이중루프를 사용하여 문제를 풀 경우 O(n^2) 시간복잡도로 인해 특정 테스트케이스에서 정해진 시간내 결과를 얻을 수 없다
• 한개의 아스크림 선택 후 비용을 정확히 맞추기 위한 값을 가진 나머지 아이스크림을 찾아 내는 것이 포인트
• 나머지 아이스크림의 위치를 찾기 위해 binary-search 가 사용된다.

이진검색이란

일반적으로 정렬된 배열에서 특정 값을 찾을 때 인간이 사용하는 방법을 그대로 로직으로 구현한다.

1. 배열의 중간값과 찾고자하는 값을 비교
2. 운좋게 같으면 그 값의 위치를 리턴
3. 찾고자 하는 값이 중간값보다 작으면 왼쪽 배열에서 다시 이진검색 수행
4. 찾고자 하는 값이 중간값보다 크면 오른쪽 배열에서 다시 이진검색 수행

이진검색 특징

• 이미 정렬된 자료구조가 필요하다
• 시간복잡도: O(Logn)

풀이

코드 데모

코드리뷰

• 정렬 후에도 아이스크림의 아이디값 정보를 유지하기 위해 16라인이 반드시? 필요
• binarySearch 함수에서 s가 e 보다 커지는 경우에 대한 예외처리 필수. 없으면 무한루프에 빠질 수 있음.

Ref.

• https://ko.wikipedia.org/wiki/이진_검색_알고리즘