이진 탐색

왜 이 문제를 푸나요?

정렬된 데이터에서 탐색 범위를 절반씩 버리는 사고를 익히기 위한 문제입니다. 경계 갱신을 정확히 하지 않으면 무한 반복이나 누락이 생기는 이유도 확인합니다.

오름차순으로 정렬된 서로 다른 정수 리스트에서 target의 인덱스를 반환하세요. 없으면 -1을 반환합니다. 선형 탐색이나 list.index()는 사용하지 않습니다.

binary_search(numbers, target)

시간 O(log n), 공간 O(1)

실행하면 아래 순서대로 채점합니다. print() 출력도 이 순서대로 쌓입니다.

#	이름	`numbers`	`target`	기대값
1	중간값 발견	`[1, 3, 5, 7, 9]`	`7`	`3`
2	양 끝	`[2, 4, 8, 10]`	`2`	`0`
3	값이 없음	`[1, 4, 6, 11]`	`5`	`-1`
4	빈 리스트	`[]`	`1`	`-1`
5	마지막 값	`[1, 3, 8, 12]`	`12`	`3`

Python 표준 라이브러리는 사용할 수 있습니다. 함수 이름과 매개변수는 제시된 형태를 유지하세요.