[음악 재생] DOUG 로이드 : 선형 검색 알고리즘 우리입니다 배열의 요소를 찾을 수 있습니다. 알고리즘 리콜 단계별 집합이다 작업을 완료하기위한 지침. 

선형 검색 다음과 같이 알고리즘이 작동합니다. 왼쪽에서 배열을 통해 반복 바로, 지정된 요소를 찾고. 

의사에서 어느입니다보다 이 문장의 증류 버전, 첫 번째 요소 인 경우 어떤 당신은, 당신이 중지 할 수 있습니다 찾고 있습니다. 그렇지 않으면, 다음 요소로 이동할 당신이 찾을 때까지 반복해서 계속 요소, 또는 당신은하지 않습니다. 그래서 우리는 선형을 사용할 수 있습니다 검색 알고리즘, 예를 들면, 목표 값을 찾기 위해 이 배열의 구. 그런데 우리는 처음부터 시작. 우리가있어 무슨 경우 를 찾고, 우리는 중지 할 수 있습니다. 그것은, 우리는 11 찾고 아니에요 아니에요. 그래서 그렇지 않으면, 다음 요소로 이동합니다. 

그래서 우리는 23 봐. 우리가 찾고있는 23인가? 아니 글쎄, 그래서 우리는 다음 단계로 이동 다음 요소, 우리는을 통해 계속 반복해서이 과정 이상, 때까지 우리는 착륙 이 같은 상황에. 

아홉, 우리가 찾고있는 것입니다 하고 배열의 요소 , 그것의 값은 아홉이다. 그래서 우리는 우리가하는지 발견 를 찾고, 우리는 중지 할 수 있습니다. 선형 검색이 성공적으로 완료되었습니다. 

그러나 우리는 무엇을 찾고있는 경우에 대해 우리의 배열에없는 요소입니다. 선형 검색이 여전히 작동합니까? 잘해야합니다. 그래서 우리는이 과정을 반복 첫 번째 요소에서 시작. 우리가있어 무슨 경우 를 찾고, 우리는 중지 할 수 있습니다. 그것은 아니다. 그렇지 않으면, 우리는 다음 요소로 이동합니다. 

그러나 우리는이 과정을 계속 반복 할 수 있습니다 차례로 각 요소를 검사, 우리는 숫자 50를 찾을 것으로 기대. 그러나 우리는 알고하지 않습니다 우리는 수 (50)를 발견했습니다 우리가하지 않았다 경우 또는, 우리는 계단 때까지 배열의 모든 단일 요소를 통해. 

단지 우리가 수행 한 번 그와 짧은 올 우리는 결론을 내릴 수있다 (50)는 배열이 아니다. 그래서 선형 검색 알고리즘, 실패한 아니라, 그 자체. 하지만 의미에서 그 일에 실패했습니다 무엇 우리는 어떻게 그것을 물었다. 

그것은로 실패했다 그것은 50을 찾지 못한만큼, 그러나 50 어레이에 없었다. 그러나 우리는 철저하게 수색 모든 단일 요소를 통해 그래서, 동안을 우리는 발견되지 않았다 무엇이든, 선형 검색 여전히 성공하더라도 소자 배열이 아니다. 

그래서 최악의 경우입니다 선형 검색과 시나리오? 그런데 우리는을 통해보고있다 모든 단일 요소, 하나 때문에 대상 요소 배열의 마지막 요소이고, 또는 우리가 찾고있는 요소는하지 않습니다 실제로 모든 배열에 존재한다. 최선의 시나리오는 무엇입니까? 그런데 우리는을 찾을 수 있습니다 즉시 요소입니다. 그리고 얼마나 많은 요소 우리는보고해야합니까 가장 좋은 경우에, 우리는을 찾고 있다면 우리는 처음에 그것을 발견? 우리는 즉시 중지 할 수 있습니다. 

이에 대해 뭐라고 이야기 선형 검색의 복잡성? 그럼 최악의 경우, 우리가 모든 단일 요소 보는. 그리고 그것은 아에서 실행 N, 최악의 경우. 

가장 좋은 경우에, 우리는거야 즉시 요소를 찾을 수 있습니다. 그리고 1의 오메가에서 실행됩니다. 

나는 더그 로이드입니다. 이 CS50입니다.