Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [선형 검색]
[패트릭 슈 미드, 하버드 대학교]
[이 CS50 수 있습니다.] [CS50.TV]
검색은 아마 당신은 더 자주 당신이 생각하는 것보다는 수행하는 일입니다.
물론, 때마다 당신은 웹 브라우저를 열고
웹 페이지 및 검색 -
좋아하는 소셜 네트워킹 사이트에 대한 귀하의 친구 또는 검색 -
당신이 검색되어 있습니다.
하지만 그건 당신이 매일 수행하는 검색의 극히 일부입니다.
당신이 옷장에 그 파란 셔츠를 찾을하려는 경우,
행사 또는 그 완벽한 빨간 블라우스
당신은 검색 중입니다.
당신은 전에 한번도 가본 적이있는 가게에 가서 때,
그리고 당신은 농산물 통로에 브로콜리를 찾고
당신은 검색 중입니다.
당신은 발견하기 시작했을 수 있습니다 무엇
그게 당신이 찾는 무엇인지에 따라
방법이나 항목이 구성되어 있습니다 당신은 그들을 찾고 때
당신이 검색하는 방법에 효과가 있습니다.
예를 들어, 셔츠 옷장 속에 걸려있는 경우,
당신은 아마 많은 검색없이를 선택할 수 있습니다.
당신이 가정하는 경우 통로를 걸어해야
브로콜리를 얻을, 당신은 아마 다른 모든 야채를 볼 필요가
그 브로콜리를 찾기 전에.
또는 알고리즘 - 선형 검색 하나의 검색 방법의 예입니다.
이름이 있듯이,
이 방법은 다른 후 하나는 선형 방식으로 항목을 검색합니다.
그래서 당신은 당신의 좋아하는 검색 엔진의 결과를보고 할 때
그리고 당신은 결과의 목록을 아래로 읽어
당신은 선형 검색을 사용하고 있습니다.
좋아요. 가 예를 들어 보자.
2, 4, 0, 5, 3, 7, 8, 1 - 우리가 번호 목록을 말해봐 -
우리는 숫자 0을 찾고 있어요.
분명히, 당신은 0 세 번째 위치에 있는지 알 수 있습니다.
그러나 컴퓨터 프로그램은 운이 없습니다.
그것은 한 번에 하나의 번호 "를 참조하십시오"할 수 있습니다.
따라서, 목록의 시작 부분에서 시작
그것은 단지 2 "보고".
이 프로그램은 다음 검사 - 2는 0과 동일?
분명히 없습니다. 그럼 다음 숫자 4로갑니다.
4 평등 0 있습니까? 아뇨.
다음, 0. 아! 제로는 0와 동일합니다.
이 우리가 있어요! 이 세 번째 위치에 있습니다.
좋아요. 의 일부 의사 살펴 보도록하겠습니다.
단지 긴 줄 정도이지만,에서 한 번에 하나의 라인을 볼 수있게 해줘 있어요.
첫째,의는 함수를 정의하게 - 그리고 우리는 선형 검색 전화 할거야 -
그리고 두 인수를 - 키 배열을.
핵심은, 우리가 찾고있는 바로 그 값이다
그래서 앞의 예에서, 그 제로이었다.
배열은 숫자의 목록입니다
우리가 검색 할거야 모든 값이 있습니다.
그럼, 우리가 원하는 것은 우리가 쳐다 봐줬으면입니다 -
모든 위치에서, 그래서 배열의 처음에서 시작
배열의 맨 끝 전까지 - 배열의 길이 때문에 -
모든 단일 위치에서보고 각각을 확인합니다.
그래서 그 일이 그 "에 대한"루프는 무엇을하고 있는지.
그리고 각 위치에서, 우리는 무슨 말을
"우리가 찾고있는 키와 같은 그 현재 위치에서 해당 값인가?"
그래서 - 앞의 예에서 다시 키는 10 살때 -
우리가 말하는 것은 "위치에서 난 0 이상 배열인가?"
이 경우, 우리는 우리가에있는 현재 위치이기 때문에 '나는'을 반환거야.
따라서 앞의 예에서,
그 세 번째 위치했다.
우리는 전체 배열을 겪었 한 경우
우리는 아무 것도 못 찾았 -
그래서 우선은 우리가 숫자 500을 찾고 말
어떤 명확하게 그 예에 아니 었어 -
우리는 뭔가를 반환해야합니다
우리는 -1 반환거야.
그 위치이기 때문에 그리고 우리는 -1을 반환하고
그 배열에 존재하지 않습니다.
그리고 그 말은 당신이 함수에서 돌아올 때 의미
는 "음, 좋아. 내가 아무 것도 찾을 수 없을 것 같네요 말합니다.
있도록 500 건 없어. "
선형 검색에 대한 좋은 것은,
그것은 항목의 목록에서 작동됩니다
에 관계없이 항목이 정렬되는 방식.
브로콜리는 농산물 계신 곳 그건 중요하지 않습니다.
당신이 처음부터 끝까지 통로를 걸어하는 한,
당신은 그것을 발견 할 의무가 있지
가게를 가정하는 것은 물론, 브로콜리 부족하지 않았습니다.
그러나 가장 큰 장점은 또한 가장 큰 약점이다.
당신은 이백 번호 목록을 말
그는 1에서 200까지 정렬됩니다.
당신은 번호 198을 찾고 계신다면,
당신은 숫자의 거의 전체 목록을 검색 할 수 있습니다
당신이 찾고있는 하나를 찾기 전에.
더 좋은 방법이있을거야!
휴식이 있습니다 안심하시기 바랍니다.
그러나, 또 다른 동영상에 대한 주제입니다.
또한, 무서워하지 마!
선형 검색은 모든 상황에서 가장 좋은 방법이 아닙니다,해서
그것이 유용하지 않는다는 것을 의미하지 않습니다.
그렇지 않으면, 당신은 농산물 통로에 해당 브로콜리을 찾을까요?
내 이름은 패트릭 슈미트 있으며,이 CS50입니다.
[CS50.TV]