가능하다면 나를 검색해라!!선형 및 바이너리 검색

 
그룹에서 항목을 검색할 때 기본적인 방법은 무엇입니까?유행하는 indexOf 방법에 익숙하거나, 함수식 프로그래밍 양식에 정통하면 find 또는 findIndex 경종을 울릴 수 있습니다.만약 어느 날 이런 편리한 수조 방법이 너에게서 사라진다면?솔루션을 직접 구현하는 방법은 무엇입니까?오늘 우리는 어떻게 자주적으로 실현되는 검색 알고리즘을 토론할 것이다.

선형 검색

이것은 아마도 네가 취할 수 있는 가장 유치한 방법일 것이다. 거의 무모한 방법일 것이다.이 알고리즘은 처음부터 주어진 그룹을 순환하고 모든 값을 제공된 일치하는 값과 비교하기만 하면 된다.일치하는 첫 번째 인덱스를 되돌려줍니다. 그렇지 않으면false를 되돌려줍니다.

linearSearch([1,2,3,4,5], 5)

function linearSearch(arr, match) {
  for(let i=0; i<arr.length; i++) {
    if(arr[i] === match) {
      return i;
    }
  }
  return false;
}

간단하죠?
선형 검색 알고리즘을 사용하는 장점 중 하나는 들어오는 그룹을 정렬할 필요가 없다는 것이다.어레이가 [3,1,4,2,5]처럼 혼란스러워 보일 수 있지만 여전히 작동합니다.실제로 우리는 기본적으로 Array.indexOf 방법을 실현했을 뿐이다😄
단점이 뭐예요?만약 수조가 수천 개의 값을 포함한다면, 우리의 일치가 마지막 색인으로 지정될 것이라고 상상해 보세요.더 심각한 것은, 전혀 일치하지 않는다면?우리 컴퓨터에 대해 말하자면, 큰 숫자를 한 조로 교체해서 계산하는 것은 매우 시간과 힘을 들인다.나는 우리가 더 잘할 수 있다고 생각한다.By the way, because we are using a single loop, it's O(n) complex.

바이너리 검색

바이너리 검색에서, 우리는 검색 간격을 반으로 줄여서 우리의 일치성을 찾습니다.일치하는 항목을 찾을 때까지 입력 그룹을 길이의 절반에 따라 하위 그룹으로 반복해서 나누는 것을 고려하십시오.이것은 매우 효과적일 것이다!이렇게 효율적이어서 시간의 복잡도는 O(logn)에 불과하다.다음은 그것의 작업 원리다.중간 값이 일치 값보다 작으면 일치 값이 뒤에 있고 그 값이 중간 값보다 크다는 뜻입니다(즉, 일치하는 값이 있는 경우).만약 중간의 값이 일치하는 값보다 크다면, 우리는 수조의 앞부분에서 다시 검색할 수 있다.씻기와 중복, 분할과 정복!이제 몇 가지 코드로 설명합시다.

function binarySearch(arr, match) {
  let start = 0; // first index
  let end = arr.length - 1; // last index
  let middle = (start + end) / 2; // middle index
}

이것은 우리의 시작 코드입니다. 매우 간단합니다.arr로 전송[1,2,3,4,5]하면 "(0+4)/2=2"를 초래하고 색인 2곳은 우리의 중간수입니다.하지만 함정을 조심해야 해!수조의 길이가 홀수일 때만 우리의 중간값이 정확한 정수 인덱스입니다.짝수 길이의 그룹을 설명하기 위해서 세 번째 줄을 약간 수정합시다.

  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

수학이 없어요.층, 전입 [1,2,3,4] 1.5.그것을 사용하면 숫자를 1로 반올림하기 때문에 중간의 숫자는 그룹의 숫자 2를 가리킨다.지금은 우리 알고리즘의 주요 부분이다.

function binarySearch(arr, match) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

  while(arr[middle] !== match) {
    if(match > arr[middle]) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  return middle;
}

중간 값이 일치하는 값과 같을 때까지while 순환을 만들었습니다.순환 내부에서, 만약 우리의 일치가 현재의 중간값보다 크다면, 이것은 우리의 일치가 수조의 하반부에서 찾을 수 있다는 것을 의미한다.따라서 우리는 시작지수 1을 중간지수보다 큰 위치로 옮겨 상반기를 안전하게 배제할 수 있다.만약 우리의 경기 규모가 비교적 작다면, 우리의 경기는 전반전에 속하여, 우리의 최종 지수 1을 중간 지수보다 작게 할 것이다.이것은 우리의 수조가 반드시 정렬 수조여야 한다는 것을 의미한다.
우리는 단지 수조를 반으로 축소했을 뿐이기 때문에 수정된 시작이나 끝으로 중간값을 다시 설정해야 한다.일치하는 항목을 찾은 다음 색인을 되돌릴 때까지 반복합니다.
위대하다하지만 패턴에 일치하는 것이 없으면...우리가while 순환 중의 조건은 영원히 회전하며 무한 순환을 초래할 것이다.이게 해결책이야.

function binarySearch(arr, match) {
  let start = 0;
  let end = arr.length - 1;
  let middle = Math.floor((start + end) / 2);

  while(arr[middle] !== match && start <= end) {
    if(match > arr[middle]) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
    middle = Math.floor((start + end) / 2);
  }

  if(arr[middle] === match) {
    return middle;
  }
  return false;
}

무슨 변화가 생겼습니까?while 순환 조건과 우리의 귀환 문장!중간 값이 일치하는 항목을 찾지 못했을 때 순환을 계속 실행하는 것을 제외하고, start가 end보다 작거나 같은지 확인합니다. start가 end보다 클 때 순환은 "그룹에 일치하는 항목이 없습니다."라고 말할 수 있습니다.그리고 물러나.한 장면을 상상하면 우리는 [1,3,5]와 [6]를 통해 일치한다.우리는 우선 지수 1과 값 3을 중간값으로 하는데 6이 3보다 크기 때문에 지수 2로 변하기 시작하면 끝과 같기 때문에 중간값도 2로 변한다.중간 값이 일치하는 값과 같은지 확인하기 위해 순환을 다시 실행합니다. 이렇게 하지 않기 때문에 한 방향으로 시작 또는 종료 1을 이동합니다. 따라서 다음 교체에서 시작이 끝보다 크기 때문에 순환이 실행되지 않습니다.
만약 우리가 최종적으로 수조에서 일치하는 항목을 찾게 된다면, 색인을 되돌려 주십시오.그렇지 않으면 false를 반환합니다.

요약

선형 검색의 쓰기와 논리는 모두 직관적이기 때문에 우리는 정렬된 그룹을 전달할 필요가 없다.하지만 속도가 느리다.BinarySearch는 훨씬 빠르지만 논리적으로 더욱 도전적이며 전송된 그룹을 정렬해야 한다.따라서 만약에 빅데이터 집합을 사용한다면 이진 검색 알고리즘을 사용하세요!😉 읽어주셔서 감사합니다!