본고에서, 나는 자바스크립트로 검색을 소개하려고 시도할 것이다.그것은 어떤 복잡한 검색 알고리즘도 아니고 일반적으로 사용하는 더욱 간단한 알고리즘이다.Javascript는 indexOf includes find 및 기타 여러 가지 검색 방법을 제공합니다.우리가 여기서 중점을 두는 것은 어떻게 이런 방법의 판본을 실현하는가이다.
우리는 본고에서 두 가지 알고리즘을 소개할 것이다. 그것이 바로 선형 검색과 2진 검색이다.
우선 인코딩 환경이다.로컬이나 온라인에서 원하는 편집기를 사용할 수 있습니다.하지만 여기서 나는 구글 브라우저 세션을 사용할 것이다.우리의 코드는 순수한javascript가 될 것이기 때문에 우리는 어떤 화려한 환경도 필요로 하지 않는다.구글 크롬의 개발 도구ctrl + shift + I를 따르고 싶다면.sources 옵션 카드를 누르고 왼쪽 내비게이터에서 snippets를 선택하십시오.새 코드 세그먼트를 만들고 linearSearch로 이름을 지정합니다.

위 그림의 아래쪽과 같이 ctrl + Enter 실행 코드를 사용할 수 있습니다.이제 시작합시다.

선형 검색

모든 자바스크립트 검색 방법, 예를 들어 find, indexOf 등은 선형 검색을 사용합니다.이것은 가장 간단한 검색 방식이다.그룹을 지정합니다. 우리는 모든 요소를 보고 우리가 찾으려는 내용을 찾습니다.우리는 그룹의 시작이나 끝에서부터 한 번에 하나의 항목을 검사한다.만약 우리가 목록이 하나 있다면const list = [12, 45, 48, 5, 451, 2,34 ,43,54,66 ]우리는 수색해야 한다2.데이터가 이 그룹에서 정렬되지 않았기 때문에 가장 좋은 방법은 그룹의 모든 항목을 순환하고 현재 교체가 같은지 확인하는 것이다2
간단하죠?
코드를 작성합시다.우리는 이 문제를 어떻게 처리할 것입니까?우리 그것을 몇 부분으로 나누자.

youguessed itlinearSearch라는 함수를 작성합니다.이 함수는 두 개의 매개 변수를 받아들일 것이다.배열과 값.

이 함수에서, 우리는 전체 그룹을 훑어보고, 현재 항목이value인지 검사할 것입니다.

이 값을 찾으면 index 값을 반환합니다. 그렇지 않으면 false 또는 -1

값을 반환합니다.
첫걸음
두 개의 매개 변수를 받아들이는 함수

var linearSearch = (list,value)=>{}

구글 크롬 코드 세그먼트를 사용하고 const 또는 let 를 사용하려면 let 를 사용하십시오. const 를 사용하면 변수를 다시 설명할 수 없기 때문에 구글 크롬 컨트롤러가 오류를 통과할 것입니다.
두 번째 단계
먼저 list 및 value 을 생성합니다.함수는 두 개의 매개 변수가 필요하다.

let linearSearch = (list,value)=>{}

var list =  [12, 45, 48, 5, 451, 2,34 ,43,54,66 ]
var value = 2;

linearSearch(list , value) // call the function with arguments

이제 우리는 논리를 실현할 것이다.

 let linearSearch = (list,value)=>{
    for (let i = 0; i < list.length; i++) {
        if (list[i] === value) {
            return i;
        }
    }
    return -1;
}

var list =  [12, 45, 48, 5, 451, 2,34 ,43,54,66 ]
var value = 2;

linearSearch(list , value) // result should 5

순환 중에 무슨 일이 일어났는지 알아봅시다.
우리는 수조 중의 원소를 arr[0] 라고 할 수 있는데, 이것은 우리에게 첫 번째 값을 주고, arr[1] 우리에게 두 번째 값을 줄 것이다.
그것의 실제 효과를 봅시다

우리의 순환 중i은 0에서 9로 증가할 것이다.매번 교체할 때, 우리는 이 인덱스list의 list[i]에서 값을 얻어 우리의 매개 변수 값과 비교할 것이다.
우리는 우리의 코드 단편 중의 debugger 을 통해 이 점을 증명할 수 있다

나는 네 번째 줄에 추가debugger를 눌렀다.f9를 누르면 점차적으로 교체되는 것을 볼 수 있다.위의 단계는 일치하는 항목을 찾는 단계입니다(6단계와 i = 5.(좌측) 패널에서 액세스할 수 있는 모든 변수를 볼 수 있습니다.
디버거를 사용하여 Blockcall StackBlock 및 local 범위를 보는 것이 좋습니다.
만약 우리가 일치하는 항목을 찾지 못한다면, 우리는 global 권 밖으로 돌아갈 것이다.
참고: 회로 외부 회로-1마지막 단계
값이 없음 -1 의 조건을 확인합니다.

너무 좋아요.그것은 지금 일하고 있다
* 선형 검색에서 배열을 정렬하거나 정렬을 취소할 수 있다는 것을 기억하십시오. 가장 좋은 상황은 바로 우리가 찾으려는 항목을 찾는 것입니다. 최악의 경우 우리가 필요로 하는 항목은 배열의 마지막 항목입니다.소형 어레이의 경우 정상적으로 작동할 수 있지만 대형 어레이의 경우 성능이 좋지 않을 수 있습니다.
이제 2진 검색으로 넘어가겠습니다.

바이너리 검색

작업 방식 때문에, 2진 검색은 속도가 더 빠른 알고리즘이다.주어진 모든 점에서 배열의 절반을 없앴다.
그러나 유일하게 주의해야 할 것은 정렬 그룹에만 적용된다는 것이다.
작업 원리
수조는 정렬된 것이기 때문에, 우리는 수조의 중점을 선택한다.중점을 설정한 후, 우리는 우리가 찾으려는 값이 중점보다 크거나 작은지 검사할 것이다.만약 이 값이 중점보다 크다면 이것은 우리의 값이 중점의 오른쪽에 있다는 것을 의미하기 때문에 우리는 왼쪽(또는 옆보다 작음)을 필요로 하지 않기 때문에 우리는 왼쪽을 포기하고 오른쪽을 본다.우리는 우리의 가치를 찾을 때까지 계속 이렇게 할 것이다.
곤혹스러웠어
우리 상상해 봅시다.먼저 그룹을 정의합니다.

let list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30];

만약에 우리가 찾고 있다면 list우리는 3분 20, left, right 이 필요하다middle left = 2중점은 right = 30 또는 14일 수 있습니다.선택 16우리의 중점은 14, 우리의 값은 14, 그래서 우리는 20에서 2의 왼쪽을 제거할 것이다
저희 어레이가 지금 이렇게 보여요.

let list = [16, 18, 20, 22, 24, 26, 28, 30];

우리의 다음 중점은 14 과 22 사이의 값이 될 것입니다. 우리는 24 과 22, left = 16 을 선택할 것입니다.
우리의midright = 30를 보면 우리의 가치((22)가 더 높습니까 아니면 더 낮습니까?이것은 그다지 정확하지 않다.?그래서 이번에 오른쪽 항목을 뺐어요.
우리의 새로운 어레이는 이렇게 될 것이다

let list = [16, 18, 20, 22];

중점20좌18우16.
우리의 가치는 보다 크다 22

let list = [20, 22];

​ 18
중점 = = 값

세 가지 순환에서 우리는 우리의 가치를 발견했다.만약 우리가 선형 검색도 이렇게 한다면, 대략 10개의 순환이 있어야만 값을 찾을 수 있다mid point === 202진 검색이 훨씬 빠르다.그러나 정렬 데이터에만 적용됩니다.
코드를 작성합시다.그렇다면 우리는 이 문제를 어떻게 처리해야 합니까?곰곰이 생각해 봅시다.

우리는 함수를 작성할 것이다. 이 함수는 두 개의 매개 변수를 받아들인다. 정렬 그룹과 값이다.

우리는 좌우 지침이 필요하다.따라서, 우리는 변수 20 를 만들 것이다. 그 값은 그룹의 첫 번째 항목이고, 오른쪽 변수의 값은 그룹의 마지막 항목이 될 것이다

우리는 left와 left의 평균치에서 얻을 수 있는 중점이 하나 더 필요하다

mid== 값까지 순환합니다.

이 값을 찾으면 인덱스로 돌아갑니다. 이 값

만약 값이 너무 작다면, 우리는 왼쪽 바늘을 이전 중점으로 옮기고, 중점을 다시 계산할 것이다

값이 너무 크면 오른쪽 바늘을 아래쪽으로 옮겨서 값을 찾을 때까지 유추합니다.

값을 찾지 못하면 right 또는 false로 돌아갑니다.

HWW.이것은 매우 많지만, 우리 한 걸음 한 걸음 완성합시다.
함수, 정렬 그룹, 값을 정의합시다.

let BinarySearch = (list,val)=>{}

let list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]
let val = 20;

우리는 세 개의 지침이 필요하다.-1 , left , right

  let left = 0;
  let right = list.length - 1;
  let mid = Math.floor((left + right) / 2);

mid은left입니다. 수조는 0 인덱스이기 때문에 수조의 첫 번째 항목은 0 인덱스에 있습니다.0 마찬가지로 수조는 0 인덱스이기 때문에 마지막 항목을 얻기 위해 우리는 그 길이에서 1을 줄일 것이다.right 평균치를 계산하기 위해 우리는 이 공식mid을 사용한다.우리는 10진수를 필요로 하지 않기 때문에javascript 내장 방법(left + right) / 2을 사용합니다.사용 가능Math.floor()스토리지에서 while loop 순환

let BinarySearch = (list,val)=>{
    let left = 0;
    let right = list.length - 1;
    let mid = Math.floor((left + right) / 2);

    while (list[mid] !== val && left <= right) {
        if (val < list[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
        mid = Math.floor((left + right) / 2);
    }
    if (list[mid] === val) {
        return mid;
    } else {
        return -1
    }

}
;

let list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]
let val = 20;
// should return 9

BinarySearch(list, val);

무섭죠.?한번 봅시다.
우선, 우리는while 순환을 이해하려고 시도할 것이다

 while (list[mid] !== val) {
        if (val < list[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
        mid = Math.floor((left + right) / 2);
    }

첫 줄에서, 우리는 현재 교체 항목이 값과 같지 않을 때까지 순환한다고 말한다.
순환 중, 우리는 우리의 조건을 검사한다
만약 우리의 값 (20) 이 현재 교체 항목보다 작다면, 이것은 우리가 오른쪽 끝을 가운데로 옮겨야 한다는 것을 의미한다.
그렇지 않으면, 이 값은 현재 교체 항목보다 크므로, 우리의 왼쪽은 중간으로 이동해야 한다.
매번 교체될 때마다 우리는 중간점을 다시 계산하고 있다.우리가 오류 값을 제공하기 전에, 상술한 코드는 정상적으로 작동할 것이다.
일치하지 않거나 일치하지 않으면 무한 순환에 처합니다.그러니까 잘 처리해야 돼.
우선, 우리는 코드가 Math.ceil() 보다 크거나 같기를 희망합니다.
따라서 상기 코드를 수정합니다.

  while (list[mid] !== val && left <= right) { // <-- modified
        if (val < list[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
        mid = Math.floor((left + right) / 2);
    }

그리고 우리의 중점이 우리가 찾으려는 값과 같은지 확인한 다음 left 로 돌아가십시오. 그렇지 않으면 right

while (list[mid] !== val && left <= right) {
        if (val < list[mid]) {
            right = mid - 1
        } else {
            left = mid + 1
        }
        mid = Math.floor((left + right) / 2);
    }

// add this code
    if (list[mid] === val) {
        return mid;
    } else {
        return -1
    }

테스트를 해보도록 하겠습니다.

가짜 값을 가지다

결론

2진 검색과 선형 검색은 모두 각자의 장단점을 가지고 있다.선형 검색은 수조의 모든 항목을 순환하는데, 대형 수조에서는 성능이 비교적 떨어진다.그러나 모든 유형의 패턴에 적용됩니다.다른 한편, 2진 검색은 훨씬 빠를 수 있지만, 이런 알고리즘의 단점은 정렬 그룹에만 적용된다는 것이다.