[이분 탐색]

모든 영역을 전체 탐색하는 방법

• 그 중 정렬된 배열의 내용을 탐색!
• start, end, mid를 이용함.
• start와 end의 중간 인덱스로 mid를 선택
• 이 값이 찾고자 하는 값보다 큰 경우 start를 mid+1로, 작은 경우 end를 mid-1로 결정
• mid의 값이 찾고자 하는 값과 일치하는 경우 (해 존재) or start가 end의 뒤로 가는 경우 (해 존재 X) 탐색 종료
• 시간 복잡도 : O(log N)

같이 볼 예제

• 수 찾기
• 랜선 자르기

참고 문제

• 백준 단계 "이분 탐색"