이진 탐색1 [이진 탐색] 백준 1920 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘으로 시간 복잡도는 nlogn이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터 크기를 절반씩 줄이면서 대상을 찾는다. 탐색 방법 1. 데이터에서 중앙값(median)을 선택한다. 2. 중앙값>타깃 데이터 라면, 중앙값을 기준으로 왼쪽 데이터셋을 선택한다. 3. 반대인 경우라면 오른쪽 데이터셋을 선택한다. 4. 1~3을 반복하면서 중앙값 == 타깃 데이터를 찾는다. 더보기 내가 찾고자 하는 데이터 = 55 3 7 13 15 23 35 38 41 46 49 55 57 68 72 77 68 -> 오름차순으로 배열 되어있는 상태, 중앙값을 41로 설정 41과 55 비교 -> 55가 더 크므로 오른쪽 데이터 셋 선택 46 49 5.. 2024. 2. 28. 이전 1 다음