1 00:00:00,000 --> 00:00:03,346 >> [음악 재생] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> DOUG 로이드 : 좋아. 4 00:00:06,220 --> 00:00:08,140 그래서 이진 검색입니다 우리가 사용할 수있는 알고리즘 5 00:00:08,140 --> 00:00:10,530 배열의 내부 요소를 찾을 수 있습니다. 6 00:00:10,530 --> 00:00:14,710 선형 검색과 달리 필요한 특별한 조건은, 미리 충족 7 00:00:14,710 --> 00:00:19,020 그러나 그것은 훨씬 더 효율적인 경우이다 상태인지, 실제로 만났다. 8 00:00:19,020 --> 00:00:20,470 >> 그래서 아이디어는 여기에 무엇입니까? 9 00:00:20,470 --> 00:00:21,780 그것은 분할과 정복이다. 10 00:00:21,780 --> 00:00:25,100 우리는의 크기를 줄이려 반 각 시간을 기준으로 검색 영역 11 00:00:25,100 --> 00:00:27,240 대상 번호를 찾기 위해. 12 00:00:27,240 --> 00:00:29,520 이 곳 조건 하지만, 활동하기 시작한다. 13 00:00:29,520 --> 00:00:32,740 우리는의 힘을 활용할 수 있습니다 요소 제거 절반 14 00:00:32,740 --> 00:00:36,070 도 보지 않고 그들은 배열을 정렬합니다. 15 00:00:36,070 --> 00:00:39,200 >> 그것은 완전한 믹스 업의 경우, 우리는 그냥 손에서 할 수 없습니다 16 00:00:39,200 --> 00:00:42,870 때문에, 소자의 절반을 버리고 우리는 우리가 폐기하는지 모르겠어요. 17 00:00:42,870 --> 00:00:45,624 그러나 배열, 분류되는 경우 우리는 그렇게 할 수있는 우리 때문에 18 00:00:45,624 --> 00:00:48,040 에 그 모든 것을 알고 우리가 현재있는 곳의 왼쪽 19 00:00:48,040 --> 00:00:50,500 보다 작아야합니다 값 우리는 현재에있어. 20 00:00:50,500 --> 00:00:52,300 그리고 모든 것에 우리가 어디의 권리 21 00:00:52,300 --> 00:00:55,040 값보다 커야 우리는 현재 찾고 있습니다. 22 00:00:55,040 --> 00:00:58,710 >> 그래서 의사는 무엇 이진 검색을위한 단계? 23 00:00:58,710 --> 00:01:02,310 우리는 때까지이 과정을 반복 배열이나, 우리는을 통해 진행으로, 24 00:01:02,310 --> 00:01:07,740 서브 어레이의 작은 조각 원래의 배열, 크기 0이다. 25 00:01:07,740 --> 00:01:10,960 중간 점을 계산 현재의 서브 어레이. 26 00:01:10,960 --> 00:01:14,460 >> 당신이 찾고있는 값의 경우 배열의 요소에, 중지합니다. 27 00:01:14,460 --> 00:01:15,030 당신은 그것을 발견했다. 28 00:01:15,030 --> 00:01:16,550 잘 됐네요. 29 00:01:16,550 --> 00:01:19,610 그렇지 않으면, 대상이면 중간에 무엇보다, 30 00:01:19,610 --> 00:01:23,430 그래서 값 경우 우리는 찾고 에 대한, 우리가 보는 것보다 낮은 31 00:01:23,430 --> 00:01:26,780 다시이 과정을 반복하지만, 대신에, 엔드 포인트를 변경 32 00:01:26,780 --> 00:01:29,300 원래되는 전체 배열을 완료, 33 00:01:29,300 --> 00:01:34,110 단지 왼쪽으로 할 수 여기서의 우리는 보았다. 34 00:01:34,110 --> 00:01:38,940 >> 우리는 중간이 너무 높은 것을 알고 있었다 또는 대상이 중간보다 작은 35 00:01:38,940 --> 00:01:42,210 그리고 그것은, 존재해야 그 경우 전혀 어레이에 존재 36 00:01:42,210 --> 00:01:44,660 어딘가에 중간 지점의 왼쪽에. 37 00:01:44,660 --> 00:01:48,120 그래서 우리는 배열을 설정합니다 바로 왼쪽에 위치 38 00:01:48,120 --> 00:01:51,145 새로운 엔드 포인트로의 중간 점. 39 00:01:51,145 --> 00:01:53,770 반대로, 대상이면 중간에 무엇보다 큰, 40 00:01:53,770 --> 00:01:55,750 우리는 똑같은 할 공정, 대신 우리 41 00:01:55,750 --> 00:01:59,520 할 시점을 변경 단지 중간 지점의 오른쪽에 42 00:01:59,520 --> 00:02:00,680 우리는 단지 계산. 43 00:02:00,680 --> 00:02:03,220 그리고, 우리는 프로세스를 다시 시작합니다. 44 00:02:03,220 --> 00:02:05,220 >> 의 확인이 시각화하자? 45 00:02:05,220 --> 00:02:08,620 그래서 가서 여기에 많이있다, 그러나 여기에서 15 요소의 배열입니다. 46 00:02:08,620 --> 00:02:11,400 그리고 우리는을 추적 할거야 더 많은 물건이 시간. 47 00:02:11,400 --> 00:02:13,870 그래서 선형 검색, 우리는 있었다 단지 목표에 대한 배려입니다. 48 00:02:13,870 --> 00:02:15,869 하지만 이번에는 우리가 원하는 우리를 어디에 관심 49 00:02:15,869 --> 00:02:18,480 보이기 시작, 어디 우리가 찾고 중지하는, 50 00:02:18,480 --> 00:02:21,876 그리고 중간 무엇 현재 배열의 형태가됩​​니다. 51 00:02:21,876 --> 00:02:23,250 그래서 여기에 우리는 이진 검색과 함께 할 것입니다. 52 00:02:23,250 --> 00:02:25,290 우리는 꽤 많은 좋은 이동하려면 맞아? 53 00:02:25,290 --> 00:02:28,650 난 그냥 내려 갈거야 인덱스의 집합 여기 아래. 54 00:02:28,650 --> 00:02:32,430 이것은 기본적으로 그냥 어떤 요소 배열의 우리에 대해 얘기하고. 55 00:02:32,430 --> 00:02:34,500 선형 검색, 우리 우리로 진대, 신경 56 00:02:34,500 --> 00:02:36,800 얼마나 많은 알 필요가 우리가 이상 반복하는 요소, 57 00:02:36,800 --> 00:02:40,010 그러나 우리는 실제로 상관 없어 무엇을 요소 우리가 현재 찾고 있습니다. 58 00:02:40,010 --> 00:02:41,014 이진 검색, 우리는 않습니다. 59 00:02:41,014 --> 00:02:42,930 그래서 사람들은있다 거기에 약간의 가이드로. 60 00:02:42,930 --> 00:02:44,910 >> 그래서 우리는 바로 시작할 수 있나요? 61 00:02:44,910 --> 00:02:46,240 음, 아주. 62 00:02:46,240 --> 00:02:48,160 내가 말한 기억 이진 검색에 대한? 63 00:02:48,160 --> 00:02:50,955 우리는 그것을 할 수 없어 다른 정렬되지 않은 배열이나, 64 00:02:50,955 --> 00:02:55,820 우리는 것을 보장하지 않습니다 특정 요소 또는 값이 없습니다 65 00:02:55,820 --> 00:02:57,650 실수로 인 폐기 할 때 우리 단지 66 00:02:57,650 --> 00:02:59,920 배열의 절반을 무시하기로 결정. 67 00:02:59,920 --> 00:03:02,574 >> 그래서 이진 검색을 한 단계 당신이 정렬 된 배열을 가지고 있어야합니다. 68 00:03:02,574 --> 00:03:05,240 그리고 당신은 정렬을 사용할 수 있습니다 우리가 얘기했습니다 알고리즘 69 00:03:05,240 --> 00:03:06,700 그 위치에 당신을 얻을 수 있습니다. 70 00:03:06,700 --> 00:03:10,370 그래서 지금, 우리는 어디에 위치에있어 우리는 이진 검색을 수행 할 수 있습니다. 71 00:03:10,370 --> 00:03:12,560 >> 그래서이 과정을 반복하자 단계별로 및 유지 72 00:03:12,560 --> 00:03:14,830 우리가 가서 무슨 일이 일어나고 있는지를 추적. 73 00:03:14,830 --> 00:03:17,980 그래서 먼저 우리는 계산하기 만하면됩니다 현재 배열의 중간 점. 74 00:03:17,980 --> 00:03:20,620 음, 우리는 먼저, 우리가있어 말할 것이다 모든 값 (19)을 찾고. 75 00:03:20,620 --> 00:03:22,290 우리는 숫자 19을 찾기 위해 노력하고 있습니다. 76 00:03:22,290 --> 00:03:25,380 이것의 첫 번째 요소 배열은, 인덱스 제로에 위치 77 00:03:25,380 --> 00:03:28,880 이 중 마지막 요소 배열은 인덱스 (14)에 위치한다. 78 00:03:28,880 --> 00:03:31,430 그래서 우리는 그 시작과 끝을 부를 것이다. 79 00:03:31,430 --> 00:03:35,387 >> 그래서 우리는 중간 점으로 계산 플러스 2 0 14에 의해 나누어 첨가하는 단계; 80 00:03:35,387 --> 00:03:36,720 매우 간단 중간 점. 81 00:03:36,720 --> 00:03:40,190 그리고 우리는 그런 말을 할 수 있습니다 중간 점은 지금 7. 82 00:03:40,190 --> 00:03:43,370 그래서 15는 우리가 찾고있는 무엇인가? 83 00:03:43,370 --> 00:03:43,940 아니, 아니에요. 84 00:03:43,940 --> 00:03:45,270 우리는 19 찾고 있습니다. 85 00:03:45,270 --> 00:03:49,400 그러나 우리는 (19)가 큰 것을 알고있다 우리는 중간에서 발견보다. 86 00:03:49,400 --> 00:03:52,470 >> 그래서 우리가 할 수있는 일입니다 시작점을 변경 87 00:03:52,470 --> 00:03:57,280 바로 오른쪽에있는 것으로 중간 점, 다시 과정을 반복합니다. 88 00:03:57,280 --> 00:04:01,690 우리가 그렇게 할 때, 우리는 지금 말 새로운 시작 포인트는 배열 위치 8입니다. 89 00:04:01,690 --> 00:04:07,220 우리가 효과적으로 수행 한 것은 (15)의 왼쪽에 무시 다. 90 00:04:07,220 --> 00:04:09,570 우리는 절반을 제거했습니다 문제의, 그리고 지금, 91 00:04:09,570 --> 00:04:13,510 대신 검색해야하는 우리의 배열의 15 요소, 92 00:04:13,510 --> 00:04:15,610 우리는 7을 통해 검색 할 수 있습니다. 93 00:04:15,610 --> 00:04:17,706 그래서 8은 새로운 시작점이다. 94 00:04:17,706 --> 00:04:19,600 14 여전히 종점이다. 95 00:04:19,600 --> 00:04:21,430 >> 그리고 지금, 우리는 다시이를 통해 이동합니다. 96 00:04:21,430 --> 00:04:22,810 우리는 새로운 중간 점을 계산합니다. 97 00:04:22,810 --> 00:04:27,130 플러스 8 14 2 11으로 나눈 22이다. 98 00:04:27,130 --> 00:04:28,660 이것은 우리가 찾고있는 무엇인가? 99 00:04:28,660 --> 00:04:30,110 아니, 아니에요. 100 00:04:30,110 --> 00:04:32,930 우리는의 값을 찾고 우리가 무엇을 발견보다. 101 00:04:32,930 --> 00:04:34,721 그래서 우리는 반복하는거야 다시 방법. 102 00:04:34,721 --> 00:04:38,280 우리는로 엔드 포인트를 변경하는거야 단지 중간 지점의 왼쪽합니다. 103 00:04:38,280 --> 00:04:41,800 그래서 새로운 엔드 포인트는 10가된다. 104 00:04:41,800 --> 00:04:44,780 그리고 지금, 그 유일한 부분 배열 우리는 통해 정렬 할 수 있습니다. 105 00:04:44,780 --> 00:04:48,460 그래서 우리는 지금 제거했다 15 요소 (12). 106 00:04:48,460 --> 00:04:51,550 우리는 알고있다 (19)의 경우 그 배열의 존재를 107 00:04:51,550 --> 00:04:57,210 요소 사이 어딘가에 존재해야합니다 번호 8, 요소 수 (10). 108 00:04:57,210 --> 00:04:59,400 >> 그래서 우리는 다시 새로운 중간 점을 계산합니다. 109 00:04:59,400 --> 00:05:02,900 8 플러스 (10)는 2 9 인으로 나누어, 18이다. 110 00:05:02,900 --> 00:05:05,074 이 경우,보고 대상은 중간에있다. 111 00:05:05,074 --> 00:05:06,740 우리는 우리가 찾고있는 정확하게 발견했다. 112 00:05:06,740 --> 00:05:07,780 우리는 중지 할 수 있습니다. 113 00:05:07,780 --> 00:05:10,561 우리는 성공적으로 완료 이진 검색. 114 00:05:10,561 --> 00:05:11,060 괜찮아. 115 00:05:11,060 --> 00:05:13,930 그래서 우리는이 알고리즘을 알고 타깃이면 작동 116 00:05:13,930 --> 00:05:16,070 어딘가에 배열의 내부. 117 00:05:16,070 --> 00:05:19,060 이 알고리즘 일 경우합니까 타겟 어레이에 있지? 118 00:05:19,060 --> 00:05:20,810 글쎄, 그것을 시작하자 또,이 때, 119 00:05:20,810 --> 00:05:23,380 의이 요소에 대해 살펴 보자 시각적으로 우리가 볼 수있는 16, 120 00:05:23,380 --> 00:05:25,620 배열의 아무 곳이나 존재하지 않습니다. 121 00:05:25,620 --> 00:05:27,110 >> 시작점은 다시 0이다. 122 00:05:27,110 --> 00:05:28,590 엔드 포인트는 다시 14이다. 123 00:05:28,590 --> 00:05:32,490 그 첫 번째의 인덱스이며 전체 배열의 마지막 요소. 124 00:05:32,490 --> 00:05:36,057 그리고 우리는 과정을 우리 그냥 통과합니다 겪은 다시 16을 찾기 위해 노력하고, 125 00:05:36,057 --> 00:05:39,140 심지어 시각적으로하지만, 우리는 이미 수 거기 될 것 아니라고 말한다. 126 00:05:39,140 --> 00:05:43,450 우리는 반드시이 알고리즘을 만들고 싶어 사실, 어떤 방법으로 여전히 작동 127 00:05:43,450 --> 00:05:46,310 그냥 우리를 떠나지 무한 루프에 갇혀. 128 00:05:46,310 --> 00:05:48,190 >> 그래서 단계는 먼저 무엇입니까? 129 00:05:48,190 --> 00:05:50,230 중간 점을 계산 현재 배열의 형태가됩​​니다. 130 00:05:50,230 --> 00:05:52,790 중간 점은 무엇인가 현재 배열의? 131 00:05:52,790 --> 00:05:54,410 음, 바로, 7입니까? 132 00:05:54,410 --> 00:05:57,560 2로 나눈 14 플러스 0 7. 133 00:05:57,560 --> 00:05:59,280 우리가 찾고있는 15인가? 134 00:05:59,280 --> 00:05:59,780 아니. 135 00:05:59,780 --> 00:06:02,930 그것은 아주 가까이,하지만 우리는 찾고 보다 약간 큰 값. 136 00:06:02,930 --> 00:06:06,310 >> 그래서 우리는 것 알고 (15)의 왼쪽에있는 곳이 될 수 없습니다. 137 00:06:06,310 --> 00:06:08,540 타겟은보다 큰 무슨 일이 중간에있다. 138 00:06:08,540 --> 00:06:12,450 그래서 우리는 새로운 시작점을 설정 다만 중간 오른쪽에있을. 139 00:06:12,450 --> 00:06:16,130 중간 점 때문에, 현재 7 의 새로운 시작점이 8 가정 해 봅시다. 140 00:06:16,130 --> 00:06:18,130 그리고 우리는 효과적으로 어떤했습니다 다시 수행 무시 141 00:06:18,130 --> 00:06:21,150 어레이의 전체 좌측 절반. 142 00:06:21,150 --> 00:06:23,750 >> 이제, 우리는 반복 한 번 더 처리합니다. 143 00:06:23,750 --> 00:06:24,910 새로운 중간 점을 계산합니다. 144 00:06:24,910 --> 00:06:29,350 플러스 8 14 2 11으로 나눈 22이다. 145 00:06:29,350 --> 00:06:31,060 우리가 찾고있는 23인가? 146 00:06:31,060 --> 00:06:31,870 불행하게도. 147 00:06:31,870 --> 00:06:34,930 우리는 값을 찾고 그 미만 (23)이다. 148 00:06:34,930 --> 00:06:37,850 그리고이 경우, 우리는거야 종점을 변경하는 것은 단지 될 149 00:06:37,850 --> 00:06:40,035 현재 중간 지점의 왼쪽에. 150 00:06:40,035 --> 00:06:43,440 현재의 중간 점 (11)이며, 그래서 우리는 새로운 엔드 포인트를 설정합니다 151 00:06:43,440 --> 00:06:46,980 우리가 갈 다음에 대한 10이 과정을 통해. 152 00:06:46,980 --> 00:06:48,660 >> 다시 말하지만, 우리는 다시 과정을 통해 이동합니다. 153 00:06:48,660 --> 00:06:49,640 중간 점을 계산합니다. 154 00:06:49,640 --> 00:06:53,100 2로 나누어 8 플러스 (10)는 9입니다. 155 00:06:53,100 --> 00:06:54,750 우리가 찾고있는 19인가? 156 00:06:54,750 --> 00:06:55,500 불행하게도. 157 00:06:55,500 --> 00:06:58,050 우리는 여전히 찾고 보다 작은 숫자입니다. 158 00:06:58,050 --> 00:07:02,060 그래서 우리는 종점이 시간을 변경합니다 단지 중간 지점의 왼쪽에있을 수 있습니다. 159 00:07:02,060 --> 00:07:05,532 중간 점은, 현재 9입니다 그래서 종점 8 일 것이다. 160 00:07:05,532 --> 00:07:07,920 그리고 지금, 우리는 찾고 단일 요소 배열에서. 161 00:07:07,920 --> 00:07:10,250 >> 이 배열의 중간 점은 무엇입니까? 162 00:07:10,250 --> 00:07:13,459 글쎄, 그것은, 8에서 시작 8시에 종료, 중간 점은 8입니다. 163 00:07:13,459 --> 00:07:14,750 그것은 우리가 찾고있는 무엇인가? 164 00:07:14,750 --> 00:07:16,339 우리는 17를 찾고 계십니까? 165 00:07:16,339 --> 00:07:17,380 아니, 우리는 (16)를 찾고 있습니다. 166 00:07:17,380 --> 00:07:20,160 이 배열에 존재한다면, 그것은 어딘가에 존재해야합니다 167 00:07:20,160 --> 00:07:21,935 우리는 현재의 위치를​​ 왼쪽. 168 00:07:21,935 --> 00:07:23,060 그래서 우리가 할 건가요? 169 00:07:23,060 --> 00:07:26,610 그래서, 우리는 단지 수 종점을 설정할 것 현재 중간 지점의 왼쪽에. 170 00:07:26,610 --> 00:07:29,055 그래서 우리는 7 종료점을 변경할 것이다. 171 00:07:29,055 --> 00:07:32,120 당신은 무엇 단지를 볼 수 있나요 하지만, 여기에 일이? 172 00:07:32,120 --> 00:07:33,370 지금 여기 봐. 173 00:07:33,370 --> 00:07:35,970 >> 시작은 이제 끝보다 더 크다. 174 00:07:35,970 --> 00:07:39,620 효과적으로, 양단 우리의 배열의 교차 한 175 00:07:39,620 --> 00:07:42,252 그리고 시작점이다 지금 종점 후. 176 00:07:42,252 --> 00:07:43,960 글쎄, 그건하지 않습니다 바로, 어떤 의미가? 177 00:07:43,960 --> 00:07:47,960 그래서 지금, 우리가 말할 수있는 것은 우리는 크기 0의 하위 배열을 가지고있다. 178 00:07:47,960 --> 00:07:50,110 그리고 한 번 우리를 받고있어 이 때, 우리가 지금 할 수있는 179 00:07:50,110 --> 00:07:53,940 해당 요소를 보장 (16) 어레이에 존재하지 않는, 180 00:07:53,940 --> 00:07:56,280 시작점 때문에 과 끝 지점이 교차했다. 181 00:07:56,280 --> 00:07:58,340 그리고 그것은이 아니다. 182 00:07:58,340 --> 00:08:01,340 자,이 약간 것을 알 시작 지점과 끝 다른 183 00:08:01,340 --> 00:08:02,900 같은 것을 가리 킵니다. 184 00:08:02,900 --> 00:08:05,030 우리는 찾고 있었다면 도 17의 경우,했을 185 00:08:05,030 --> 00:08:08,870 배열하고, 시작 지점에 있었다 마지막 반복과 끝 지점 186 00:08:08,870 --> 00:08:11,820 그 점은 교차하기 전에, 우리는 거기 (17)을 발견했을 것이다. 187 00:08:11,820 --> 00:08:15,510 그들은 우리가 할 수있는 교차 할 때 그것은 단지이다 요소가되지 않도록 보장 188 00:08:15,510 --> 00:08:17,180 배열에 존재한다. 189 00:08:17,180 --> 00:08:20,260 >> 그럼 훨씬 적은 보자 선형 검색보다 단계. 190 00:08:20,260 --> 00:08:23,250 최악의 시나리오에서는 있었다 n 개의 요소의 목록을 분할 191 00:08:23,250 --> 00:08:27,770 반복적으로 반으로, 대상을 찾을 수 하나 때문에 대상 요소 192 00:08:27,770 --> 00:08:33,110 마지막 어딘가에있을 것입니다 분할, 또는 전혀 존재하지 않습니다. 193 00:08:33,110 --> 00:08:37,830 최악의 경우 그래서, 우리는에있다 당신이 알고 array-- 분할? 194 00:08:37,830 --> 00:08:40,510 n 배의 로그; 우리 문제를 절단해야 195 00:08:40,510 --> 00:08:42,610 시간의 절반 특정 수있다. 196 00:08:42,610 --> 00:08:45,160 배의 수는 로그 N입니다. 197 00:08:45,160 --> 00:08:46,510 >> 최선의 시나리오는 무엇입니까? 198 00:08:46,510 --> 00:08:48,899 음, 처음으로 우리 중간 지점을 계산 199 00:08:48,899 --> 00:08:50,190 우리는 우리가 원하는 것을 찾을 수 있습니다. 200 00:08:50,190 --> 00:08:52,150 모든 이전에 이진 검색에 예 201 00:08:52,150 --> 00:08:55,489 우리가 있던 경우에 우리는 단지, 이상 갔어요 소자 (15)을 찾고, 202 00:08:55,489 --> 00:08:57,030 우리는 즉시 발견했을 것이다. 203 00:08:57,030 --> 00:08:58,321 즉, 처음에 있었다. 204 00:08:58,321 --> 00:09:01,200 즉의 중간 점이었다 분할의 첫 번째 시도 205 00:09:01,200 --> 00:09:03,950 이진 검색 부문의. 206 00:09:03,950 --> 00:09:06,350 >> 그리고 최악의 경우는, 이진 검색이 실행 207 00:09:06,350 --> 00:09:11,580 실질적으로 더 나은 로그 N에서 최악의 경우에 선형 탐색보다. 208 00:09:11,580 --> 00:09:16,210 최상의 경우에서, 이진 검색 결과 1의 오메가에서 실행됩니다. 209 00:09:16,210 --> 00:09:18,990 그래서 이진 검색을 많이입니다 선형 검색보다 더 나은, 210 00:09:18,990 --> 00:09:23,270 하지만 당신은 과정을 처리해야 당신이 할 수있는 전에 먼저 배열을 정렬 211 00:09:23,270 --> 00:09:26,140 이진 검색의 힘을 활용. 212 00:09:26,140 --> 00:09:27,130 >> 나는 더그 로이드입니다. 213 00:09:27,130 --> 00:09:29,470 이 CS 50입니다. 214 00:09:29,470 --> 00:09:31,070