[음악 연주] 

ZAMYLA CHAN : 당신이 수있는 우선 발견에 대한 통지는 우리 이미 코드는 우리를 위해 작성했습니다. 이는 유통 코드라고합니다. 그래서 우리는 우리 자신을 작성하지 않을 더 이상 처음부터 코드입니다. 오히려, 우리는 빈 공간에 작성하고 일부 기존 코드. 

find.c 프로그램 번호를 입력하라는 메시지 건초 더미를 채우기 위해 검색 사용자가 제출 haystack에서 needle, 그것은 종류를 호출하여이 작업을 수행 검색, 기능 정의 helpers.c합니다. 그래서 find.c 이미 기록됩니다. 당신의 임무는 도우미를 작성하는 것입니다. 

그래서 우리는 무엇을하고 있습니까? 우리는 두 가지 기능을 구현하고 있습니다. true를 반환하는 검색의 경우 값 반환, 건초 더미에서 발견된다 잘못된 값이있는 경우 하지 건초 더미에서. 그리고 우리는 또한 정렬을 구현하고 어떤 값이라는 배열을 정렬합니다. 

그래서 검색을 해결할 수 있습니다. 검색은 현재로서 구현 선형 검색,하지만 당신은 많은 작업을 수행 할 수 있습니다 보다 더 나은. 선형 검색은 O로 구현 N 시간으로, 이는 매우 느리다. 하지만, 검색하여 그에게 주어진 모든 목록. 당신의 임무는 이진 검색을 구현​​하는 것입니다, 로그 n의 시간이 O를 실행하고있다한다. 그건 꽤 빠르다. 

그러나 규정이있다. 이진 검색은 검색 할 수 있습니다 사전 정렬 된 목록을 통해. 그 이유는 무엇입니까? 

음의 예를 살펴 보자. 값의 배열을 지정해, 건초 더미, 우리가 찾고있을거야 바늘. 이 예에서, 정수 세. 이진 검색이 작동하는 방식은 그 우리의 중간 값을 비교 많은 같은 바늘로 배열하는 방법 우리는 중간에 전화 번호부를 열어 주 제로의 페이지. 

그래서에 중간 값을 비교 한 후 바늘, 당신은 하나를 취소 할 수 있습니다 왼쪽이나 배열의 우측 절반 당신의 경계를 조여. 이 경우, 세시기, 우리 바늘 10 이하, 중간 값이다 바로 바인딩은 줄일 수 있습니다. 하지만 당신의 경계를 만들기 위해 노력하고 가능한 한 단단한. 중앙값은 바늘없는 경우 당신은 당신이 필요하지 않은 것을 알고 검색에 포함. 그래서 잘되어있어 조 수 조금도 더 많은 검색 범위, 등 등까지 당신은 당신의 바늘을 찾을 수 있습니다. 

그래서 의사가 보입니까? 우리는 여전히를 찾고있는 동안 잘 목록 여전히에 요소가 에서 보면, 우리는 목록의 중간을 하고 그 중간 값을 비교 우리의 바늘. 가 동일한 경우에, 그 다음 우리가했습니다 의미 바늘을 발견하고 우리가 할 수 true를 반환합니다. 

그렇지 않으면, 바늘보다 작 으면 중간 값은, 그 다음 우리에게 의미 오른쪽 절반을 버리고, 그냥 할 수 있습니다 어레이의 왼쪽을 검색. 그렇지 않으면, 우리는 검색합니다 배열의 오른쪽. 그리고 마지막에, 경우에 당신은 어떤이 없습니다 더 많은 검색 왼쪽 요소가 있지만, 당신은 아직 당신의 바늘을 발견하지 않았습니다 false를 반환하기 때문에 바늘 확실히 건초 더미에 있지 않습니다. 

이 의사에 대한 지금 깔끔한 것 이진 검색에있을 수 있다는 것입니다 반복적 인 중 하나로 해석 또는 재귀 구현. 당신이 호출하면 그래서 재귀 것 검색 내에서 검색 기능 배열의 어느 반에 작동합니다. 우리는 조금 나중에에서 재귀를 다룰 것 물론, 그러나임을 알지 옵션 당신이 시도하고 싶은 경우. 

이제 종류를 살펴 보자. 배열을 정렬하고 정수 소요 배열의 크기 N,. 지금은 여러 가지 종류가 있습니다 종류의, 당신은 몇 가지를 볼 수 있습니다 데모와 설명을위한 반바지. 반환 형식 우리의 정렬 기능은 무효입니다. 그래서 우리는하지 않을거야 것을 의미합니다 종류에서 어떤 배열을 반환합니다. 우리는 실제로 매우을 바꿀 것입니다 우리로 전달 된 배열입니다. 

배열이 있기 때문에 그게 가능 우리는 지금 C. 참고로합니다 전달 나중에 이것에 대해 더 많은 것을 볼 수 있지만, 통과 사이의 중요한 차이 정수 및 전달과 같은 뭔가 배열에서, 그 때 정수를 전달, C 단지 예정 그 정수의 복사본을 만들고 전달 함수에. 원래 변수는 변경되지 않습니다 함수가 완료되면. 배열로, 한편, 그것의 정보 복사본을 만들려고, 당신은거야하지 실제로 편집 할 수 매우 배열 자체. 

그래서 종류의 한 종류입니다 선택 정렬. 선택 정렬에서 시작하여 작동 당신이 반복하고 시작하고, 에 가장 작은 요소를 찾을 수 있습니다. 그리고 당신은 교환이 작은 첫 번째와 요소입니다. 그리고 두 번째 요소로 이동 , 다음으로 작은에게 찾아 다음 요소 및 교환이있는 배열의 두 번째 요소 때문에 첫 번째 요소는 이미 정렬됩니다. 그리고 당신은 모든 계속 최소를 식별하는 요소 가치와 그것을 교환. 

I는 0, 최초의 요소에 해당 내용은 N - 1, 당신은 비교거야 모든 다음 그 후 값 찾기 최소값의 인덱스. 당신이 최소 값의 인덱스를 찾아 내면, 당신은 배열의 값을 바꿀 수 있습니다 최소 배열 I. 

종류의 또 다른 유형의 당신이 할 수 구현은 거품의 일종이다. 목록에 따라서 버블 정렬을 반복 인접 요소와 비교 엘리먼트를 교환하는 잘못된 순서로되어 있습니다. 그리고이 방법의 가장 큰 요소 거품이 끝까지 것이다. 그리고 목록은 한 번 더 이상 분류되지 않습니다 요소가 교체되었습니다. 

그래서 사람들은 종류의 두 가지 예 당신이 구현할 수있는 알고리즘 찾기 프로그램. 당신은 종류 완료, 당신은 일단 검색을 수행하면 완성입니다. 내 이름은 Zamyla이며,이 CS50입니다. 

[음악 연주]