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

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

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

검색은 현재 구현 선형 검색으로. 하지만 당신은 그보다 훨씬 더 할 수 있습니다. 선형 검색은 N의 O로 구현 아주 느린 시간,하지만, 이것은 그에게 주어진 모든 목록을 검색 할 수 있습니다. 당신의 임무는 이진 검색을 구현​​하는 것입니다, 로그 n의 시간이 O를 실행하고있다한다. 그건 꽤 빠르다. 

그러나 규정이있다. 이진 검색은 검색 할 수 있습니다 사전 정렬 된 목록을 통해. 그 이유는 무엇입니까? 음, 예를 살펴 보자. 값의 배열을 지정해, 건초 더미, 우리가 찾고있을거야 바늘과이에 예를 들어, 정수 3. 

이진 검색이 작동하는 방식은 그 우리의 중간 값을 비교 많은 같은 바늘로 배열하는 방법 우리는 중간에 전화 번호부를 열어 주 0 페이지. 그래서에 중간 값을 비교 한 후 바늘, 당신은 하나를 취소 할 수 있습니다 왼쪽이나 배열의 우측 절반 당신의 경계를 조여. 이 경우, 3 이후 우리 바늘이고, 10 이하, 중앙값, 바로 바인딩은 줄일 수 있습니다. 

하지만 당신의 경계를 만들기 위해 노력하고 가능한 한 단단한. 중앙값은 바늘없는 경우 당신은 당신이 필요하지 않은 것을 알고 검색에 포함. 그래서 바인딩 권리는 조 수 조금도 더 많은 검색 범위, 등 등, 때까지 당신은 당신의 바늘을 찾을 수 있습니다. 

그래서 의사는 무엇을합니까 코드처럼? 음, 우리는 아직까지보고있는 동안 목록 여전히이 에서 볼 수있는 요소는, 우리는 중간을 목록과 그 비교 우리의 바늘 중간 값. 가 동일한 경우에, 그 다음 우리가했습니다 의미 바늘을 발견, 우리는 할 수있다 true를 반환합니다. 

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

자,이 의사에 대한 하나의 깔끔한 것 이진 검색의 코드는이 수 반복적 하나로서 해석 될 또는 재귀 구현. 당신이 호출하면 그래서 재귀 것 검색 내에서 검색 기능 배열의 어느 반에 작동합니다. 우리는 재귀를 조금 다룰 것 이후 과정에서. 그러나이 옵션임을 알 수 있습니까 당신이 시도하려는 경우.