이진 탐색 개요00:04
이진 탐색은 정렬된 데이터에서 특정 값을 찾는 알고리즘입니다.
선형 탐색과의 차이점:
선형 탐색은 정렬 여부와 관계없이 작동하지만, 이진 탐색은 반드시 정렬된 데이터에서만 사용할 수 있습니다.
이진 탐색은 데이터의 반절을 나누어 탐색 방향을 결정합니다.
이진 탐색의 원리00:41
이진 탐색은 특정 기준(예: 7, 9)을 설정하여 찾으려는 값과 비교합니다.
예시: 1부터 100까지의 업다운 게임을 통해 이진 탐색의 개념을 설명합니다.
중간값을 기준으로 값이 크거나 작은지에 따라 탐색 방향을 결정합니다.
시간 복잡도: O(log N)으로, 선형 탐색보다 효율적입니다.
이진 탐색 구현03:51
입력값: 검색할 타겟과 데이터 리스트를 받습니다.
예시 데이터: [1, 3, 5, 7, 9, 11, 10, 3, 15], 타겟: 5
초기값 설정:
start = 0, end = 데이터 길이 - 1
반복문: start가 end보다 작거나 같을 때까지 반복합니다.
중간값(mid) 계산: mid = (start + end) // 2
중간값과 타겟 비교:
같으면 mid 반환
작으면 start를 mid + 1로 업데이트
크면 end를 mid - 1로 업데이트
라이브러리 사용07:17
바이섹트 라이브러리를 사용하여 이진 탐색을 구현할 수 있습니다.
left와 right를 설정하여 탐색 방향을 결정합니다.
예: 여러 개의 값이 있을 때, left는 첫 번째 인덱스를, right는 다음 인덱스를 찾습니다.
주의사항 및 결론09:24
알고리즘을 사용할 때는 논리 구조가 바뀔 수 있다는 점에 유의해야 합니다.
이진 탐색의 원리를 이해한 후, 다양한 방법으로 적용할 수 있는 능력을 기르는 것이 중요합니다.