>> ROB 보덴은 : 안녕, 난 롭 해요.
우리는 어떻게 이진 검색을 사용합니까?
찾아 보자.
그래서,이 검색은 우리가 가고 있습니다 재귀 적으로 구현합니다.
또한 이진 검색을 구현​​할 수 반복적으로, 그래서 당신은 그런 적이있는 경우,
그것은 완벽하게 괜찮아요.
>> 이제 첫째, 기억합시다 무엇 검색에 대한 매개 변수가 될 것을 의미한다.
여기, 우리는 int 값을 참조 사용자가 값이고 가정
에 대한 검색.
우리는 INT 값 배열을 참조하는 우리가 야하는 배열
값을 검색.
그리고 우리는이다, INT의 N 참조 우리의 배열의 길이.
>> 자, 우선 처음.
우리는 n이에, 0에 해당하는지 확인 우리는 false를 반환하는 경우.
우리가 비어있는 경우 그건 그냥 말하는 것 배열 값은 명확하지 않습니다
하늘의 배열은, 그래서 우리는 false를 반환 할 수 있습니다.
>> 이제, 우리는 실제로 바이너리를 수행 할 이진 검색의 검색 부분.
그래서, 우리는 중간을 찾으려면 이 배열의 요소입니다.
여기, 우리는 중간 분할 N에 해당 말 이 기준, 중간 요소이기
의 길이 될 것 우리는이 어레이에 의​​해 분할.
이제 우리는 확인하려고하는 경우 중간 요소는 우리가하고있는 값과 동일
에 대한 검색.
값의 중간 값에 해당 그렇다면, 우리 우리가 발견 한 이후 true를 반환 할 수 있습니다
우리의 배열에있는 값입니다.
>> 그러나 그것은 사실이 아니었다면, 지금 우리는 재귀을 할 필요가
이진 검색의 단계.
우리는에 하나를 검색해야 배열 또는 왼쪽
배열의 중간.
중간에 값이있는 경우, 그래서 여기에 우리는 말 값보다 작은, 즉 그 값을 의미한다
중간보다 큰 배열의 형태가됩​​니다.
그래서 값의 오른쪽에 있어야 우리가 바라 보았다 요소입니다.
>> 그래서 여기, 우리는거야 재귀 적으로 검색 할 수 있습니다.
그리고 우리는 우리가 통과하는지 살펴 보자 두 번째로이에.
그러나 우리는에 검색 할거야 중간 요소의 권리.
다른 경우에, 그 의미 값이 중간보다 작은
배열, 그리고 우리는거야 왼쪽에있는 검색하십시오.
이제 왼쪽이 될 것입니다 좀 더 쉽게 볼 수 있습니다.
그래서, 우리는 우리가 반복적으로 걸 여기 참조 여기서 첫 번째 검색을 호출
인수는 다시 값입니다 우리는 이상 찾고 있습니다.
두 번째 인수는 될 것입니다 우리가 이상 찾고 있다고 배열입니다.
그리고 마지막 요소는 지금 중간입니다.
마지막 매개 변수는 우리의 int이며 기억 N, 즉 우리의 배열의 길이의 때문에.
>> 검색하는 재귀 호출에서, 우린 지금 말하는 그 길이
배열은 중간입니다.
그래서, 우리의 배열은 크기 20 그리고 우리의라면 중간이기 때문에, 인덱스 10에서 검색
(20)를 2로 나눈, 그것은 우리가있어 의미 새로 (10)를 통과
우리의 배열의 길이.
기억하십시오 당신은 배열이있을 때 길이 10, 그 유효한 수단
요소는 0에서 9까지의 인덱스에 있습니다.
그래서 이것은 우리가 원하는 정확히 무엇입니까 왼쪽 - 업데이트 된 배열을 지정
중간 엘리먼트의 배열.
>> 그래서 오른쪽으로 찾고 있습니다 조금 더 어렵습니다.
이제 첫째, 길이를 생각해 보자 오른쪽에 배열
중간 요소입니다.
그래서, 우리의 배열의 크기 n의 인 경우, 다음 새로운 배열의 크기 n을 뺀 될 것입니다
중간 - 1.
그래서, N 마이너스 중간 생각하자.
>> 또, 배열의 사이즈가 20 인 경우와 우리는 중간을 얻기 위해 2로 나누어,
그래서 중간은 10, n은 마이너스 중순 우리가 10, 그래서 10을 제공하는 것입니다
중간의 오른쪽에있는 요소입니다.
그러나 우리는 또한이 마이너스가 1, 우리는 원하지 않기 때문에
중간 자체 있습니다.
그래서 N 마이너스 중간에서 1을 뺀 우리에게 제공 오른쪽에있는 요소의 총 수
배열의 중간 색인.
>> 지금 여기, 기억이 중간 매개 변수 값의 배열입니다.
그래서 여기, 우리를 전달하고 업데이트 된 값의 배열입니다.
이 값이 플러스 중간에 1을 더한입니다 실제로 재귀 적으로 호출 말
검색, 새로운 배열을 전달 곳 이 새로운 배열은 중앙에서 시작
플러스 우리의 원래 값의 배열의 하나.
>> 그에 대한 대체 구문, 지금 당신은 포인터를 참조하기 시작했습니다
앰퍼샌드 값 중간 플러스 1.
따라서, 중간의 주소를 잡아 값을 더한 요소입니다.
>> 자, 당신은 편안하지 않다면 당신은 그와 같은 배열을 수정
또한 사용하여이를 구현 한 수 재귀 도우미 기능, 위치
그 도우미 기능을합니다 이상의 인수.
그래서 대신 값을 취하는, 배열 및 배열의​​ 크기
도우미 기능이 더 걸릴 수 있습니다 낮은 인덱스 등의 인수,
당신은 배열에 대한 관심 것 그리고 당신이 걱정 상단 인덱스
배열에 대해.
>> 그리고 모두 이하의 트랙을 유지 인덱스와 인덱스 상단에, 당신은하지 않습니다
지금까지 수정해야하는 원래 값의 배열입니다.
당신은 계속 할 수 있습니다 값 배열을 사용합니다.
그러나 여기에서, 우리는 도우미가 필요하지 않습니다 통지 로 우리가있어로서 기능
원본을 수정하고자 값의 배열입니다.
우리는에 전달하고자하는 업데이트 된 값.
>> 이제, 우리는 이상의 이진 검색을 할 수 없습니다 정렬되지 않은 배열입니다.
그래서,이 정리하세요.
자, 그 종류는 과거입니다 알 두 매개 변수는 어떤 값을 int로
우리가 분류하고 배열 ​​및 INT의 N, 어레이의 길이 인 것을
우리는 분류하고 있습니다.
그래서, 우리가 구현하려는 정렬 알고리즘
즉, N의 O를 제곱입니다.
당신은 버블 정렬, 선택을 선택할 수 정렬이나 삽입 정렬, 또는
우리가하지 않은 다른 종류의 클래스에서 본.
그러나 여기에서, 우리는 갈거야 선택 정렬을 사용합니다.
>> 그래서, 우리는 반복하는거야 전체 배열에 대해.
자, 우리는 우리가 반복하는 것을 볼 수 0에서 N으로 - 1.
왜 모든 방법 N까지?
음, 우리는 이미 정렬 한 경우 첫 번째 다음 N - 1 요소,
이미 무엇을해야 가장 마지막 요소 올바른 위치에, 그래서 위에 정렬
전체 배열.
>> 자, 기억하는 방법을 선택 종류의 작동합니다.
우리는 전체 배열에 갈거야 의 최소​​값을 찾는
배열과 스틱이 처음에.
그럼 우리는 전체에 갈거야 배열은 두 번째로 다시 찾고
작은 요소, 스틱이 에서 두 번째 위치에있는
배열, 등등.
그래서, 이것이 무엇을하고 있는지입니다.
>> 여기에서, 우리는 우리가 걸보고있다 현재 최소 설정
i 번째 인덱스 값입니다.
그래서 첫 번째 반복에, 우리는거야 최소 값이라고 생각합니다
우리 어레이의 시작.
그 후, 우리는 반복하는거야 에 체크 배열의 나머지
보다가 어떤 요소가 더 작은 경우 참조 우리가 현재하고있는 일
최소 고려.
>> 그래서 여기, 일본을 더한 값 - 그건 우리가 현재 무엇보다
최소 고려.
그런 다음 업데이트 할 거냐 우리는 최소한에 생각
인덱스 J + 1.
따라서, 전체 어레이에 걸쳐 그렇게, 이 후 루프, 최소
에서 최소의 요소해야 배열에서 i 번째 위치.
>> 우리가이되면, 우리는 교체 할 수 있습니다 i 번째의 위치로 최소값
배열.
그래서 이것은 단지 표준 스왑입니다.
우리는 임시 값을 저장 - 배열에있는 i 번째 값 -
배열에있는 i 번째 값에 넣고 이 속해있는 최소값,
다음 위치로 다시 저장 로 사용되는 현재의 최​​소값
배열에있는 i 번째 값, 그래서 우리는 그것을 잃지 않았다.
>> 그래서 그것은 계속된다 다음 반복.
우리는 두 번째를 찾기 시작합니다 최소값에 해당 삽입
두 번째 위치.
세 번째 반복에서 우리를 찾을 수 있습니다 세 번째 최소 값과 삽입
그 세 번째 위치에, 등등 우리는 정렬 된 배열을 가지고 때까지.
내 이름은 롭이며,이 선택 정렬했다.