[JSアルゴリズム]探索アルゴリズム(線形探索、バイナリ探索、Naive String Search)
13182 ワード
せんけいたんさく
가장 간단한 방법
配列内のすべての要素を表示し、必要な値であるかどうかを確認する.배열
に対する様々な検索方法がある.function linearSearch(arr, val) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) return i;
}
return -1;
}
console.log(linearSearch([34, 56, 1, 2], 1));
バイナリサーチ
훨씬 빠르다
절반을 제거
次に、残りの部分について同じ手順を繰り返します.정렬된 배열
Divide and Conquer
方式. - 이 함수는 정렬된 배열과 검색할 값을 인수로 받는다.
- 배열의 시작 부분에 왼쪽 포인터를 만들고 배열의 끝 부분에 오른쪽 포인터를 만들고, 중간 포인터도 만든다.
- 검색한 값과 중앙 포인터의 값이 같지 않으며서 왼쪽 포인터가 오른쪽 포인터 앞에 오는 동안:
- 값이 크면 오른쪽 포인터를 중앙 포인터의 왼쪽으로 이동
- 값이 작으면 왼쪽 포인터를 중앙 포인터의 오른쪽으로 이동
- 좌우 포인터의 중간 인덱스로 중앙 포인터를 재설정
- 검색한 값과 중앙 포인터 값이 같은 경우, 해당 중앙 포인터 반환하고 이외에는 -1 반환
function binarySearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while (arr[middle] !== elem && start <= end) {
if (elem < arr[middle]) end = middle - 1;
else start = middle + 1;
middle = Math.floor((start + end) / 2);
}
return arr[middle] === elem ? middle : -1;
}
console.log(
binarySearch(
['apple', 'banana', 'cola', 'dexter', 'eft', 'finder', 'google'],
'google'
)
);
Naive String Search
- 두 문자열(긴 문자열, 찾는 패턴)을 받는 함수를 정의한다.
- 긴 문자열 루프를 돈다.
- 짧은 문자열(찾는 패턴) 루프를 돈다.
- 만약 문자가 일치하지 않으면, 내부 루프에서 벗어난다.
- 문자가 일치하면 계속 진행한다.
- 내부 루프(짧은문자열 루프)를 완료하고 일치하는 항목을 찾으면 일치 횟수를 증가시킨다.
function naiveStringSearch(long, short) {
let count = 0;
for (let i = 0; i < long.length; i++) {
for (let j = 0; j < short.length; j++) {
if (long[i + j] !== short[j]) break;
if (j === short.length - 1) count++;
}
}
return count;
}
console.log(naiveStringSearch('wowomgzomg', 'omg')); // 2
Reference
この問題について([JSアルゴリズム]探索アルゴリズム(線形探索、バイナリ探索、Naive String Search)), 我々は、より多くの情報をここで見つけました https://velog.io/@jangws/5.-검색-알고리즘선형-검색-이진-검색-Naive-String-Searchテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol