전화번호부에서 "박XX"의 전화번호를 찾고 있는 중이라고 가정해보자.
책을 한장 한장 넘기면서 찾는다면... 그것은 hell일 것이다. 😈
"박"씨 성이니까 책 중간 어디쯤부터 찾는 게 더 효율적일 것이다.
이런 문제를 "탐색 문제"라고 하고
이런 경우 "이진 탐색"이라는 알고리즘을 사용해 문제를 해결할 수 있다.
이진탐색이 뭐에요?
정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘이다.
장점 : 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다.
단점 : 중간 값을 찾아야하기 때문에 정렬된 리스트에만 사용할 수 있다.
동작 방식
1. 배열의 중간 값을 임의의 값으로 가져온다.
2. 중간 값과 찾는 값을 비교
중간 값 = 찾는 값 : 찾았다! 검색 종료!
중간 값 > 찾는 값 : 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색
중간 값 < 찾는 값 : 중간 값 기준 배열의 오른쪽 구간을 대상으로 탐색
3. 값을 찾거나 간격이 0이 될 때까지 반복
댓글