자바스크립트 데이터 구조의 검색 알고리즘 및 Algorithm_javascript 기술

데이터를 찾는 방법에는 순차 검색과 이진 검색이 있습니다. 순차 검색은 무작위로 배열된 요소가 있는 목록에서 작동합니다. 이진 검색은 정렬된 요소 목록에서 작동합니다. 이진 검색은 더 효율적이지만 정렬된 목록 요소 집합이어야 합니다.

1: 순차검색
순차검색은 목록의 첫 번째 요소부터 시작하여 원하는 결과를 찾을 때까지, 또는 목록 끝까지 원하는 요소를 찾을 수 없을 때까지 목록 요소를 하나씩 판단하는 것입니다.

코드는 다음과 같습니다.

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return true;
    }
  }
  return false;
}

요소의 위치에 맞는 순차 검색 기능을 반환할 수도 있습니다. 코드는 다음과 같습니다.

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return i;
    }
  }
  return -1;
}

둘: 최소값과 최대값 찾기

배열에서 최소값을 찾는 알고리즘은 다음과 같습니다.

1. 배열의 첫 번째 요소를 변수에 할당하고 이 변수를 최소값으로 사용합니다.
2. 두 번째 요소부터 시작하여 배열 탐색을 시작하고 이를 현재 최소값과 비교합니다.
3. 현재 요소의 값이 현재 최소값보다 작은 경우 현재 요소를 새로운 최소값으로 설정합니다.
4. 다음 요소로 이동하여 3단계를 반복하세요.
5. 프로그램이 종료되면 이 변수에 저장되는 것은 최소값입니다.

코드는 다음과 같습니다.

function findMin(arr) {
  var min = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

최대값을 찾는 알고리즘은 위의 최소값과 유사합니다. 먼저 배열의 첫 번째 요소를 최대값으로 설정한 다음 배열의 나머지 각 요소를 현재 최대값과 비교하는 루프를 반복합니다. 현재 요소의 값이 현재 최대값보다 큰 경우 해당 요소의 값을 최대값에 할당합니다. 코드는 다음과 같습니다.

function findMax(arr) {
  var max = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
 }

셋: 이진 검색 방법.

찾고 있는 데이터가 순서대로 정렬된 경우에는 순차 검색 알고리즘보다 이진 검색 알고리즘이 더 효율적입니다. 이진 탐색 알고리즘의 기본 원리는 다음과 같습니다.

1. 배열의 첫 번째 위치를 하한(0)으로 설정합니다.
2. 배열의 마지막 요소 위치를 상한(배열의 길이에서 1을 뺀 값)으로 설정합니다.
3. 하한 경계가 상한 경계와 같거나 작은 경우 다음을 수행합니다.
A. 중간점을 (상한 경계 + 하한 경계)를 2로 나눈 값으로 설정합니다.
B. 중간점 요소가 쿼리 값보다 작은 경우, 중간점 요소의 첨자에 1을 더한 값을 하한값으로 설정합니다.
C. 중간점에 있는 요소가 쿼리 값보다 큰 경우, 중간점 요소의 첨자에서 1을 뺀 값으로 상한을 설정합니다.
D. 그렇지 않으면 중간점 요소가 찾아야 할 데이터이고 반환될 수 있다.

코드는 다음과 같습니다.

// 二分查找算法
function binSearch(data,arr) {
var lowerBound = 0;
  var upperBound = arr.length - 1;
  while(lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound)/2);
    if(arr[mid] < data) {
      lowerBound = mid + 1;
    }else if(arr[mid] > data) {
      upperBound = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}
 // 快速排序
function qSort(list) {
  if(list.length == 0) {
    return [];
  }
  // 存储小于基准值的值
  var left = [];
  // 存储大于基准值的值
  var right = [];
  var pivot = list[0];
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      left.push(list[i]);
    }else {
      right.push(list[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 // 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));

4: 반복 횟수를 계산합니다.
이진 검색 알고리즘 binSearch() 함수가 특정 값을 찾았을 때, 데이터 세트에 다른 동일한 값이 있으면 함수는 비슷한 값 근처에 위치하게 됩니다. 즉, 다른 동일한 값이 있을 수 있습니다. 찾은 값의 왼쪽 또는 오른쪽이 나타납니다.

그러면 가장 간단한 해결책은 두 개의 루프를 작성하는 것입니다. 하나는 데이터 세트를 아래쪽이나 왼쪽으로 동시에 탐색하여 반복 횟수를 계산한 다음 위쪽이나 오른쪽으로 탐색하여 반복 횟수를 계산하는 것입니다. 코드는 다음과 같습니다.

// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var i = position -1; i > 0; --i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var i = position + 1; i < arr.length; ++i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
  }
  return arrs;
}
 // 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);

아래 그림과 같습니다.