자료가 크기 순서대로 정렬된 리스트에서 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘을 만들어 보세요. 리스트에 찾는 값이 없으면 -1을 돌려줍니다.

 

이번 문제는 숫자가 여러 개 들어 있는 리스트에서 특정한 값이 있는 위치를 돌려주고, 리스트에 그 값이 없으면 -1을 결괏값으로 돌려주는 문제 7과 똑같습니다. 다만 이번에는 리스트의 자료가 순서대로 정렬되어 있으므로 훨씬 더 빠르게 탐색할 수 있습니다.

이분 탐색(Binary search)의 이분(二分)은 ‘둘로 나눈다’는 뜻입니다. 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색하기 때문에 자료를 하나하나 찾아야 하는 순차 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있습니다.

이분 탐색에 대해 자세히 알아보기 전에 일상생활에서 경험할 수 있는 탐색 문제를 몇 가지 생각해 보겠습니다.