>> [음악 재생]
>> DOUG 로이드 : 좋아.
그래서 이진 검색입니다 우리가 사용할 수있는 알고리즘
배열의 내부 요소를 찾을 수 있습니다.
선형 검색과 달리 필요한 특별한 조건은, 미리 충족
그러나 그것은 훨씬 더 효율적인 경우이다 상태인지, 실제로 만났다.
>> 그래서 아이디어는 여기에 무엇입니까?
그것은 분할과 정복이다.
우리는의 크기를 줄이려 반 각 시간을 기준으로 검색 영역
대상 번호를 찾기 위해.
이 곳 조건 하지만, 활동하기 시작한다.
우리는의 힘을 활용할 수 있습니다 요소 제거 절반
도 보지 않고 그들은 배열을 정렬합니다.
>> 그것은 완전한 믹스 업의 경우, 우리는 그냥 손에서 할 수 없습니다
때문에, 소자의 절반을 버리고 우리는 우리가 폐기하는지 모르겠어요.
그러나 배열, 분류되는 경우 우리는 그렇게 할 수있는 우리 때문에
에 그 모든 것을 알고 우리가 현재있는 곳의 왼쪽
보다 작아야합니다 값 우리는 현재에있어.
그리고 모든 것에 우리가 어디의 권리
값보다 커야 우리는 현재 찾고 있습니다.
>> 그래서 의사는 무엇 이진 검색을위한 단계?
우리는 때까지이 과정을 반복 배열이나, 우리는을 통해 진행으로,
서브 어레이의 작은 조각 원래의 배열, 크기 0이다.
중간 점을 계산 현재의 서브 어레이.
>> 당신이 찾고있는 값의 경우 배열의 요소에, 중지합니다.
당신은 그것을 발견했다.
잘 됐네요.
그렇지 않으면, 대상이면 중간에 무엇보다,
그래서 값 경우 우리는 찾고 에 대한, 우리가 보는 것보다 낮은
다시이 과정을 반복하지만, 대신에, 엔드 포인트를 변경
원래되는 전체 배열을 완료,
단지 왼쪽으로 할 수 여기서의 우리는 보았다.
>> 우리는 중간이 너무 높은 것을 알고 있었다 또는 대상이 중간보다 작은
그리고 그것은, 존재해야 그 경우 전혀 어레이에 존재
어딘가에 중간 지점의 왼쪽에.
그래서 우리는 배열을 설정합니다 바로 왼쪽에 위치
새로운 엔드 포인트로의 중간 점.
반대로, 대상이면 중간에 무엇보다 큰,
우리는 똑같은 할 공정, 대신 우리
할 시점을 변경 단지 중간 지점의 오른쪽에
우리는 단지 계산.
그리고, 우리는 프로세스를 다시 시작합니다.
>> 의 확인이 시각화하자?
그래서 가서 여기에 많이있다, 그러나 여기에서 15 요소의 배열입니다.
그리고 우리는을 추적 할거야 더 많은 물건이 시간.
그래서 선형 검색, 우리는 있었다 단지 목표에 대한 배려입니다.
하지만 이번에는 우리가 원하는 우리를 어디에 관심
보이기 시작, 어디 우리가 찾고 중지하는,
그리고 중간 무엇 현재 배열의 형태가됩​​니다.
그래서 여기에 우리는 이진 검색과 함께 할 것입니다.
우리는 꽤 많은 좋은 이동하려면 맞아?
난 그냥 내려 갈거야 인덱스의 집합 여기 아래.
이것은 기본적으로 그냥 어떤 요소 배열의 우리에 대해 얘기하고.
선형 검색, 우리 우리로 진대, 신경
얼마나 많은 알 필요가 우리가 이상 반복하는 요소,
그러나 우리는 실제로 상관 없어 무엇을 요소 우리가 현재 찾고 있습니다.
이진 검색, 우리는 않습니다.
그래서 사람들은있다 거기에 약간의 가이드로.
>> 그래서 우리는 바로 시작할 수 있나요?
음, 아주.
내가 말한 기억 이진 검색에 대한?
우리는 그것을 할 수 없어 다른 정렬되지 않은 배열이나,
우리는 것을 보장하지 않습니다 특정 요소 또는 값이 없습니다
실수로 인 폐기 할 때 우리 단지
배열의 절반을 무시하기로 결정.
>> 그래서 이진 검색을 한 단계 당신이 정렬 된 배열을 가지고 있어야합니다.
그리고 당신은 정렬을 사용할 수 있습니다 우리가 얘기했습니다 알고리즘
그 위치에 당신을 얻을 수 있습니다.
그래서 지금, 우리는 어디에 위치에있어 우리는 이진 검색을 수행 할 수 있습니다.
>> 그래서이 과정을 반복하자 단계별로 및 유지
우리가 가서 무슨 일이 일어나고 있는지를 추적.
그래서 먼저 우리는 계산하기 만하면됩니다 현재 배열의 중간 점.
음, 우리는 먼저, 우리가있어 말할 것이다 모든 값 (19)을 찾고.
우리는 숫자 19을 찾기 위해 노력하고 있습니다.
이것의 첫 번째 요소 배열은, 인덱스 제로에 위치
이 중 마지막 요소 배열은 인덱스 (14)에 위치한다.
그래서 우리는 그 시작과 끝을 부를 것이다.
>> 그래서 우리는 중간 점으로 계산 플러스 2 0 14에 의해 나누어 첨가하는 단계;
매우 간단 중간 점.
그리고 우리는 그런 말을 할 수 있습니다 중간 점은 지금 7.
그래서 15는 우리가 찾고있는 무엇인가?
아니, 아니에요.
우리는 19 찾고 있습니다.
그러나 우리는 (19)가 큰 것을 알고있다 우리는 중간에서 발견보다.
>> 그래서 우리가 할 수있는 일입니다 시작점을 변경
바로 오른쪽에있는 것으로 중간 점, 다시 과정을 반복합니다.
우리가 그렇게 할 때, 우리는 지금 말 새로운 시작 포인트는 배열 위치 8입니다.
우리가 효과적으로 수행 한 것은 (15)의 왼쪽에 무시 다.
우리는 절반을 제거했습니다 문제의, 그리고 지금,
대신 검색해야하는 우리의 배열의 15 요소,
우리는 7을 통해 검색 할 수 있습니다.
그래서 8은 새로운 시작점이다.
14 여전히 종점이다.
>> 그리고 지금, 우리는 다시이를 통해 이동합니다.
우리는 새로운 중간 점을 계산합니다.
플러스 8 14 2 11으로 나눈 22이다.
이것은 우리가 찾고있는 무엇인가?
아니, 아니에요.
우리는의 값을 찾고 우리가 무엇을 발견보다.
그래서 우리는 반복하는거야 다시 방법.
우리는로 엔드 포인트를 변경하는거야 단지 중간 지점의 왼쪽합니다.
그래서 새로운 엔드 포인트는 10가된다.
그리고 지금, 그 유일한 부분 배열 우리는 통해 정렬 할 수 있습니다.
그래서 우리는 지금 제거했다 15 요소 (12).
우리는 알고있다 (19)의 경우 그 배열의 존재를
요소 사이 어딘가에 존재해야합니다 번호 8, 요소 수 (10).
>> 그래서 우리는 다시 새로운 중간 점을 계산합니다.
8 플러스 (10)는 2 9 인으로 나누어, 18이다.
이 경우,보고 대상은 중간에있다.
우리는 우리가 찾고있는 정확하게 발견했다.
우리는 중지 할 수 있습니다.
우리는 성공적으로 완료 이진 검색.
괜찮아.
그래서 우리는이 알고리즘을 알고 타깃이면 작동
어딘가에 배열의 내부.
이 알고리즘 일 경우합니까 타겟 어레이에 있지?
글쎄, 그것을 시작하자 또,이 때,
의이 요소에 대해 살펴 보자 시각적으로 우리가 볼 수있는 16,
배열의 아무 곳이나 존재하지 않습니다.
>> 시작점은 다시 0이다.
엔드 포인트는 다시 14이다.
그 첫 번째의 인덱스이며 전체 배열의 마지막 요소.
그리고 우리는 과정을 우리 그냥 통과합니다 겪은 다시 16을 찾기 위해 노력하고,
심지어 시각적으로하지만, 우리는 이미 수 거기 될 것 아니라고 말한다.
우리는 반드시이 알고리즘을 만들고 싶어 사실, 어떤 방법으로 여전히 작동
그냥 우리를 떠나지 무한 루프에 갇혀.
>> 그래서 단계는 먼저 무엇입니까?
중간 점을 계산 현재 배열의 형태가됩​​니다.
중간 점은 무엇인가 현재 배열의?
음, 바로, 7입니까?
2로 나눈 14 플러스 0 7.
우리가 찾고있는 15인가?
아니.
그것은 아주 가까이,하지만 우리는 찾고 보다 약간 큰 값.
>> 그래서 우리는 것 알고 (15)의 왼쪽에있는 곳이 될 수 없습니다.
타겟은보다 큰 무슨 일이 중간에있다.
그래서 우리는 새로운 시작점을 설정 다만 중간 오른쪽에있을.
중간 점 때문에, 현재 7 의 새로운 시작점이 8 가정 해 봅시다.
그리고 우리는 효과적으로 어떤했습니다 다시 수행 무시
어레이의 전체 좌측 절반.
>> 이제, 우리는 반복 한 번 더 처리합니다.
새로운 중간 점을 계산합니다.
플러스 8 14 2 11으로 나눈 22이다.
우리가 찾고있는 23인가?
불행하게도.
우리는 값을 찾고 그 미만 (23)이다.
그리고이 경우, 우리는거야 종점을 변경하는 것은 단지 될
현재 중간 지점의 왼쪽에.
현재의 중간 점 (11)이며, 그래서 우리는 새로운 엔드 포인트를 설정합니다
우리가 갈 다음에 대한 10이 과정을 통해.
>> 다시 말하지만, 우리는 다시 과정을 통해 이동합니다.
중간 점을 계산합니다.
2로 나누어 8 플러스 (10)는 9입니다.
우리가 찾고있는 19인가?
불행하게도.
우리는 여전히 찾고 보다 작은 숫자입니다.
그래서 우리는 종점이 시간을 변경합니다 단지 중간 지점의 왼쪽에있을 수 있습니다.
중간 점은, 현재 9입니다 그래서 종점 8 일 것이다.
그리고 지금, 우리는 찾고 단일 요소 배열에서.
>> 이 배열의 중간 점은 무엇입니까?
글쎄, 그것은, 8에서 시작 8시에 종료, 중간 점은 8입니다.
그것은 우리가 찾고있는 무엇인가?
우리는 17를 찾고 계십니까?
아니, 우리는 (16)를 찾고 있습니다.
이 배열에 존재한다면, 그것은 어딘가에 존재해야합니다
우리는 현재의 위치를​​ 왼쪽.
그래서 우리가 할 건가요?
그래서, 우리는 단지 수 종점을 설정할 것 현재 중간 지점의 왼쪽에.
그래서 우리는 7 종료점을 변경할 것이다.
당신은 무엇 단지를 볼 수 있나요 하지만, 여기에 일이?
지금 여기 봐.
>> 시작은 이제 끝보다 더 크다.
효과적으로, 양단 우리의 배열의 교차 한
그리고 시작점이다 지금 종점 후.
글쎄, 그건하지 않습니다 바로, 어떤 의미가?
그래서 지금, 우리가 말할 수있는 것은 우리는 크기 0의 하위 배열을 가지고있다.
그리고 한 번 우리를 받고있어 이 때, 우리가 지금 할 수있는
해당 요소를 보장 (16) 어레이에 존재하지 않는,
시작점 때문에 과 끝 지점이 교차했다.
그리고 그것은이 아니다.
자,이 약간 것을 알 시작 지점과 끝 다른
같은 것을 가리 킵니다.
우리는 찾고 있었다면 도 17의 경우,했을
배열하고, 시작 지점에 있었다 마지막 반복과 끝 지점
그 점은 교차하기 전에, 우리는 거기 (17)을 발견했을 것이다.
그들은 우리가 할 수있는 교차 할 때 그것은 단지이다 요소가되지 않도록 보장
배열에 존재한다.
>> 그럼 훨씬 적은 보자 선형 검색보다 단계.
최악의 시나리오에서는 있었다 n 개의 요소의 목록을 분할
반복적으로 반으로, 대상을 찾을 수 하나 때문에 대상 요소
마지막 어딘가에있을 것입니다 분할, 또는 전혀 존재하지 않습니다.
최악의 경우 그래서, 우리는에있다 당신이 알고 array-- 분할?
n 배의 로그; 우리 문제를 절단해야
시간의 절반 특정 수있다.
배의 수는 로그 N입니다.
>> 최선의 시나리오는 무엇입니까?
음, 처음으로 우리 중간 지점을 계산
우리는 우리가 원하는 것을 찾을 수 있습니다.
모든 이전에 이진 검색에 예
우리가 있던 경우에 우리는 단지, 이상 갔어요 소자 (15)을 찾고,
우리는 즉시 발견했을 것이다.
즉, 처음에 있었다.
즉의 중간 점이었다 분할의 첫 번째 시도
이진 검색 부문의.
>> 그리고 최악의 경우는, 이진 검색이 실행
실질적으로 더 나은 로그 N에서 최악의 경우에 선형 탐색보다.
최상의 경우에서, 이진 검색 결과 1의 오메가에서 실행됩니다.
그래서 이진 검색을 많이입니다 선형 검색보다 더 나은,
하지만 당신은 과정을 처리해야 당신이 할 수있는 전에 먼저 배열을 정렬
이진 검색의 힘을 활용.
>> 나는 더그 로이드입니다.
이 CS 50입니다.