Data Structures & Algorithms with Javascript : Searching Algorithms

[이전글] 2024.07.28 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Sorting Algorithms (Advanced)

Data Structures & Algorithms with Javascript : Sorting Algorithms (Advanced)

데이터를 탐색 방식은 크게 두 가지로 나뉜다 : sequential search와 binary search.
sequential search은 리스트가 랜덤 한 순서로 되어 있을 경우 사용되고, binary search는 정렬된 리스트에서 요소를 찾을 때 사용된다.
binary search가 좀 더 효율적이지만 탐색 이전 데이터를 정렬해줘야 한다는 걸 감안해야 한다.

오늘은 sequential search와 binary search를 구현해 보고 각각 예시를 들며 사용도 살펴보자.

Sequential Search

가장 직관적으로 데이터를 검색하는 방식은 그냥 배열의 첫 번째 요소부터 시작해서 찾으려는 요소에 도달할 때까지 리스트를 순회하는 것이다. 이런 방식으로 데이터를 검색하는 방식을 sequential 또는 linear search라고 한다. brute-force 방식이 sequential search를 활용한다.

 

sequential search 구현은 아주 단순하다. 루프를 돌면서 모든 데이터를 살펴 찾으려는 값을 찾을 때까지 반복하면 된다.

function seqSearch(arr,data){
	for(let i = 0; i < arr.length; ++i){
    	if(arr[i] === data){
        	return true; // 검색 시 값을 찾았다면 즉시 true 리턴
        }
    	return false;
    }
}

// array를 한 줄에 10개씩 띄어쓰기로 구분한 형식으로 리턴해주는 헬퍼함수
function displayArr(arr){
	return arr.reduce((acc,curr,i) => {
		acc+=curr+' ';
		if(i%10 ==9){
			acc+="\n";
		}
		return acc;
	},'')
}

// 출력 함수
const print = item => console.log(item);

let nums = Array.from({length:100},()=>Math.floor(Math.random()*101));
const num = 32;
if(seqSearch(nums,num)){
	print(`${num} is in the array`);
}else {
	print(`${num} is not in the array`);
}

print(displayArr(nums));
/**
32 is not in the array
80 80 7 5 95 40 48 14 81 49 
100 74 68 51 39 73 36 23 28 19 
55 96 52 30 85 1 11 25 71 33 
61 99 1 86 15 44 20 18 98 97 
8 99 27 97 94 81 57 80 100 77 
73 45 62 40 56 31 91 68 40 23 
27 5 31 81 74 91 88 13 55 42 
64 20 55 74 15 18 59 31 28 47 
74 62 9 73 44 23 49 6 18 8 
72 53 0 71 58 55 18 0 11 10 


*/

 

자바스크립트에는 indexOf라는 내장 함수가 있다.  

indexOf는 true/false 대신 찾으려는 값의 인덱스 혹은 없다면 -1을 리턴해준다. seqSearch가 indexOf처럼 동작하도록 수정해 보자.

function seqSearch(arr,data){
	for(let i = 0; i < arr.length; ++i){
    	if(arr[i] === data){
        	return i; // 검색 시 해당 요소가 자리한 배열의 인덱스 리턴
        }
    }
	return -1;
}

최대 최솟값 찾기 

정렬된 데이터값에서는 최대최소 값을 찾는 게 아주 쉽다. 하지만 정렬되지 않은 데이터에서 찾기에는 조금 더 신경 쓸 부분들이 있다. 다음과 같이 최솟값을 구하기 위한 로직을 생각해 볼 수 있다.

1. 배열의 첫 요소를 최솟값으로 설정한다.
2. 배열을 두 번째 요소부터 루프를 돌면서 현재 최솟값과 대소 비교를 한다.
3. 현재 요소가 현재 최솟값보다 작다면 현재 값을 새로운 최솟값으로 지정한다.
4. 다음 인덱스의 엘리먼트로 옮겨서 3번 과정을 반복한다.
5. 최솟값은 프로그램 종료 시점에는 변수로 저장되어 있어야 한다.

위의 과정을 코드로 옮겨보자.

function findMin(arr) {
    let min = arr[0];
    for (let i = 1; i < arr.length; ++i) {	// 첫째(현재 최소의 자리)가 아닌 두번째 요소부터 비교 시작
    	if (arr[i] < min) { 
        	min = arr[i];
    	} 
    }
    return min; 
}

 

최댓값을 구하는 과정도 비슷하다.

배열의 첫 요소를 최소로 지정하는 대신 최대로 지정해 주고 각 요소들을 순회하면서 대소비교를 해서 최대를 지정해 주면 된다.

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

 

👇 전체 코드

 

function seqSearch(arr,data){
	for(let i = 0; i < arr.length; ++i){
    	if(arr[i] === data){
        	return true; // 검색 시 값을 찾았다면 즉시 true 리턴
        }
    	return false;
    }
}

// array를 한 줄에 10개씩 띄어쓰기로 구분한 형식으로 리턴해주는 헬퍼함수
function displayArr(arr){
	return arr.reduce((acc,curr,i) => {
		acc+=curr+' ';
		if(i%10 ==9){
			acc+="\n";
		}
		return acc;
	},'')
}

// 출력 함수
const print = item => console.log(item);

let nums = Array.from({length:100},()=>Math.floor(Math.random()*101));

// 최소값 구하기
function findMin(arr) {
    let min = arr[0];
    for (let i = 1; i < arr.length; ++i) {	// 첫째(현재 최소의 자리)가 아닌 두번째 요소부터 비교 시작
    	if (arr[i] < min) { 
        	min = arr[i];
    	} 
    }
    return min; 
}

// 최대값 구하기
function findMax(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; ++i) {
    	if (arr[i] > max) { 
        	max = arr[i];
    	} 
    }
    return max; 
}


const minValue = findMin(nums);
const maxValue = findMax(nums);

print(displayArr(nums));
print();
print("The minimum value is: " + minValue);
print();
print("The maximum value is: " + maxValue);

/**
51 48 76 65 23 96 22 56 74 37 
38 3 6 62 44 25 73 22 76 43 
66 91 21 81 61 60 94 32 92 57 
13 8 18 57 37 12 1 78 0 55 
37 26 99 62 38 33 75 9 92 84 
75 76 48 70 100 77 94 1 65 63 
11 82 5 64 48 36 29 90 20 2 
2 52 41 39 59 10 4 18 87 13 
52 3 3 98 63 50 91 68 44 49 
0 36 40 50 41 77 56 14 96 90 

The minimum value is: 0

The maximum value is: 100
*/

 

 

 

 

Self-Organizing data

sequential search가 가장 빠르게 이루어지기 위해서는 간단히 찾으려는 요소가 배열 맨 앞에 위치하도록 하는 것이다.

자주 검색되는 데이터를 찾았다면 이 값을 배열의 맨 앞에 위치하는 방식으로 검색 시간을 줄일 수 있다. 

예를 들면, 도서관에서 인기 책이 있어 그 책의 위치를 물어보는 사람이 많다면 가까운 곳에 그 책을 비치하는 것이 좋다.

개발자가 직접 프로그램이 실행되기 전에 데이터를 정렬하는 것이 아니라 프로그램 자체가 돌아가면서 정렬을 하는 방식을 self-organized data라고 부른다.

 

self-organized data를 다룰 때 자주 검색되는 데이터를 "80-20 규칙"을 따르도록 하자.

즉, 80% 의 검색이 20%의 데이터만 찾을 경우 self-organize 하도록 하자.

self-organization을 통해 결국 자주 검색되는 20%가 데이터 배열 앞에 위치하게 되어 검색이 더 빨라진다.

80-20 규칙처럼 확률 분포 규칙들을 Pareto distributions라고 부른다. 

 

이전 seqSearch 함수에 self-organization 기능을 추가해 보자.

4가 3번이나 검색이 되기 때문에 리스트의 맨 앞으로 bubble up 되고 있는 모습을 확인할 수 있다.

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

function swap(arr, index, index1) { 
	temp = arr[index];
	arr[index] = arr[index1]; 
    arr[index1] = temp;
}

const print = item => console.log(item);

let numbers = [5,1,7,4,2,10,9,3,6,8]; 
print(numbers);
for (let i = 1; i <= 3; i++) {
   seqSearch(numbers, 4);
   print(numbers);
}

/**
[5, 1, 7, 4, 2, 10, 9, 3, 6, 8]
[5, 1, 4, 7, 2, 10, 9, 3, 6, 8]
[5, 4, 1, 7, 2, 10, 9, 3, 6, 8]
[4, 5, 1, 7, 2, 10, 9, 3, 6, 8]
*/

 

검색하려는 요소가 이미 배열 앞쪽에 위치했다면 이동을 시켜주지 않도록 하자.

80-20 규칙을 따르도록 배열 길이의 20%밖에 위치한 경우에만 이동을 시키도록 코드를 수정해 보자.

function seqSearch(arr,data){
	for(let i = 0; i < arr.length; ++i){
    	if(arr[i] === data && i > (arr.length * 0.2)){ 
			swap(arr,i,0);
            return true;
        } else if(arr[i] == data){
        	return true;
        }
    }
	return false;
}

function swap(arr, index, index1) { 
	temp = arr[index];
	arr[index] = arr[index1]; 
    arr[index1] = temp;
}

const print = item => console.log(item);

let numbers = [5,1,7,4,2,10,9,3,6,8]; 
print(numbers);
for (let i = 1; i <= 3; i++) {
   seqSearch(numbers, 4);
   print(numbers);
}

/**
[5, 1, 7, 4, 2, 10, 9, 3, 6, 8]
[4, 1, 7, 5, 2, 10, 9, 3, 6, 8]
[4, 1, 7, 5, 2, 10, 9, 3, 6, 8]
[4, 1, 7, 5, 2, 10, 9, 3, 6, 8]
*/

 

Binary Search

정렬된 데이터의 경우 sequential search보다는 binary search를 활용하는 것이 더 효율적이다.

binary search가 동작하는 방식은 다음과 같은 게임을 한다고 생각하면 된다.

 

친구랑 숫자 맞추기 게임을 한다고 해보자. 가능한 숫자는 1과 100 사이의 값이다.

숫자를 하나 외칠 때마다 친구가 대답할 수 있는 말은 다음 중 하나다.

1. 정답입니다!
2. 숫자가 너무 크다!
3. 숫자가 너무 작다!

이 게임에서는 항상 중간 위치의 숫자를 선택하는 게 점점 선택의 폭을 줄이기 때문에 유리하다.

100의 반인 50을 외쳤을 경우 정답이 더 큰 수라면 75를 외쳐보고, 작다면 25를 외친다.

다음은 정답이 82인 경우를 나타낸다.

 

만약 1부터 차례대로 외쳤다면 82번째까지 턴이 지속된다. 100을 외치더라도 18번째까지 턴이 지속된다.

하지만 중간 지점부터 외치면 6번 안에 정답을 맞힐 수 있다.

 

이제 binary search가 무엇인지 살펴봤다. binary search의 논리 흐름을 정리해보자.

1. 배열의 첫 요소의 하위 범위 (lower bound, 0)를 지정.
2. 배열의 마지막 요소의 상위 범위 (upper bound, array.length-1)를 지정.
3. 하위 범위가 상위 범위보다 작거나 같으면 
   1. 중간점(midpoint) = (상위 범위 - 하위 범위)/2로 지정.
   2. 중간점의 요소가 찾으려는 요소보다 작다면 새로운 하위 범위를 중간점 + 1로 지정
   3. 중간점의 요소가 찾으려는 요소보다 크면 새로운 상위 범위를 중간점 - 1로 지정
   4. 중간점의 요소 == 찾으려는 요소라면 중간점 반환

// 출력 함수
const print = item => console.log(item);

function binarySearch(arr,data){
	let upperBound = arr.length-1;
    let lowerBound = 0;
    while(lowerBound <= upperBound){
    	let mid = Math.floor((upperBound+lowerBound)/2);
		print(`current midpoint: ${mid}`);
        if(arr[mid]<data){
        	lowerBound = mid+1;
        } else if(arr[mid]>data){
        	upperBound = mid-1;
        } else {
        	return mid;
        }
    }
    return -1;
}

// array를 한 줄에 10개씩 띄어쓰기로 구분한 형식으로 리턴해주는 헬퍼함수
function displayArr(arr){
	return arr.reduce((acc,curr,i) => {
		acc+=curr+' ';
		if(i%10 ==9){
			acc+="\n";
		}
		return acc;
	},'')
}


// insertSort, 데이터 정렬해주기
function insertSort(arr){
		const copy = [...arr];
        let temp, inner;
        for(let outer = 1; outer <= copy.length-1; ++outer){
            temp = copy[outer];
            inner = outer;
            while(inner > 0 && (copy[inner-1] >= temp)){
                copy[inner] = copy[inner-1];
                --inner;
            }
            copy[inner] = temp;
        }
		return copy;
	}
    


let nums = Array.from({length:100},()=>Math.floor(Math.random()*101));

nums = insertSort(nums); // 정렬 이후

print(displayArr(nums));
print();

const val = 99;

let retVal = binarySearch(nums, val); 
if (retVal >= 0) {
	print("Found " + val + " at position " + retVal);
} else {
	print(val + " is not in array.");
}

/**
1 1 2 3 6 7 7 8 9 10 
10 13 13 14 14 14 16 16 18 18 
18 19 19 21 22 23 25 25 25 25 
26 27 28 29 30 31 33 34 35 35 
35 36 36 37 37 38 39 41 42 42 
42 43 45 46 48 49 50 52 52 54 
54 56 58 59 61 61 63 63 63 66 
66 66 67 70 71 71 72 73 74 75 
75 76 78 78 81 84 84 85 85 86 
87 87 87 90 90 92 93 96 96 99 

current midpoint: 49
current midpoint: 74
current midpoint: 87
current midpoint: 93
current midpoint: 96
current midpoint: 98
current midpoint: 99
Found 99 at position 99

*/

 

랜덤 값으로 배열을 채우다 보면 같은 값들이 중복되어 들어갈 수 있다.

근데 위의 배열은 찾으려는 값을 중복값들 중 가운데 값을 찾는다.

예를 들어 66이 3번 들어간 위의 데이터에서 두 번째 66의 자리를 반환한다.

 

값이 몇 번 등장하는지 나타낼 수 있도록 코드를 수정해 보자.

// 출력 함수
const print = item => console.log(item);

function binarySearch(arr,data){
	let upperBound = arr.length-1;
    let lowerBound = 0;
    while(lowerBound <= upperBound){
    	let mid = Math.floor((upperBound+lowerBound)/2);
		print(`current midpoint: ${mid}`);
        if(arr[mid]<data){
        	lowerBound = mid+1;
        } else if(arr[mid]>data){
        	upperBound = mid-1;
        } else {
        	return mid;
        }
    }
    return -1;
}

///////////////////////////////// 💖 추가 /////////////////////////////////
// 등장 빈도수 카운트
function count(arr, data){
	let count = 0;
    let position = binarySearch(arr,data);
    if(position > -1){
    	++count;
        for(let i=position-1; i>0; --i){
        	if(arr[i]==data){
            	++count;
            } else {
            	break;
            }
        }
        for(let i=position+1; i<arr.length; ++i){
        	if(arr[i]==data){
            	++count;
            } else {
            	break;
            }
        }
    }
    return count;
}
///////////////////////////////// 💖 추가 /////////////////////////////////

// array를 한 줄에 10개씩 띄어쓰기로 구분한 형식으로 리턴해주는 헬퍼함수
function displayArr(arr){
	return arr.reduce((acc,curr,i) => {
		acc+=curr+' ';
		if(i%10 ==9){
			acc+="\n";
		}
		return acc;
	},'')
}


// insertSort, 데이터 정렬해주기
function insertSort(arr){
		const copy = [...arr];
        let temp, inner;
        for(let outer = 1; outer <= copy.length-1; ++outer){
            temp = copy[outer];
            inner = outer;
            while(inner > 0 && (copy[inner-1] >= temp)){
                copy[inner] = copy[inner-1];
                --inner;
            }
            copy[inner] = temp;
        }
		return copy;
	}
    


let nums = Array.from({length:100},()=>Math.floor(Math.random()*101));

nums = insertSort(nums); // 정렬 이후

print(displayArr(nums));
print();

const val = 45;

let retVal = count(nums, val); 
if (retVal >= 0) {
	print("Found " + retVal + " occurrences of " + val + ".");
} else {
	print(val + " is not in array.");
}


/**
1 2 5 7 7 8 9 10 10 12 
13 15 15 15 15 15 16 18 18 18 
19 19 23 24 24 24 25 25 26 28 
29 31 31 33 33 33 35 35 36 36 
36 36 37 38 41 45 45 47 48 48 
49 50 50 51 51 53 54 56 56 57 
59 59 61 62 63 63 66 66 67 67 
68 69 70 71 71 72 74 75 77 77 
78 79 82 82 82 85 87 89 89 92 
92 93 93 94 94 95 97 98 98 99 

current midpoint: 49
current midpoint: 24
current midpoint: 36
current midpoint: 42
current midpoint: 45
Found 2 occurrences of 45.

*/

 

텍스트 데이터 검색

지금까지는 숫자 데이터 검색을 다뤘다. 이번에는 문자열을 검색하는 알고리즘에 대해 살펴보자.

[출처] : https://www.norvig.com/big.txt

The nationalism of Hamilton was undemocratic. The democracy of Jefferson was, in the beginning, provincial. The historic mission of uniting nationalism and democracy was in the course of time given to new leaders from a region beyond the mountains, peopled by men and women from all sections and free from those state traditions which ran back to the early days of colonization. The voice of the democratic nationalism nourished in the West was heard when Clay of Kentucky advocated his American system of protection for industries; when Jackson of Tennessee condemned nullification in a ringing proclamation that has taken its place among the great American state papers; and when Lincoln of Illinois, in a fateful hour, called upon a bewildered people to meet the supreme test whether this was a nation destined to survive or to perish. And it will be remembered that Lincoln's party chose for its banner that earlier device--Republican--which Jefferson had made a sign of power. The "rail splitter" from Illinois united the nationalism of Hamilton with the democracy of Jefferson, and his appeal was clothed in the simple language of the people, not in the sonorous rhetoric which Webster learned in the schools.

 

이 텍스트 데이터에서 "rhetoric"이라는 단어를 찾을 때 sequential search, binary search 각각으로 데이터 찾기에 걸리는 시간을 재어 보자.

처리기의 속도가 매우 빨라져서 데이터량이 엄청 많지 않은 이상 두 검색 알고리즘의 차이를 느끼기 어렵지만,

수학적으로 증명된 바로는 binary search가 검색할 아이템을 반씩 줄여가기 때문에  더 빠르다. 

// 출력 함수
const print = item => console.log(item);

// 텍스트 검색 
function seqSearch(arr, data) {
	for (let i = 0; i < arr.length; ++i) {
        if (arr[i] == data) { 
            return i;
        } 
    }
	return -1; 
}


function binarySearch(arr,data){
	let upperBound = arr.length-1;
    let lowerBound = 0;
    while(lowerBound <= upperBound){
    	let 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;
}

// insertSort, 데이터 정렬해주기
function insertSort(arr){
    const copy = [...arr];
    let temp, inner;
    for(let outer = 1; outer <= copy.length-1; ++outer){
        temp = copy[outer];
        inner = outer;
        while(inner > 0 && (copy[inner-1] >= temp)){
            copy[inner] = copy[inner-1];
            --inner;
        }
        copy[inner] = temp;
    }
    return copy;
}
    
const text = `The nationalism of Hamilton was undemocratic. The democracy of Jefferson was, in the beginning, provincial. The historic mission of uniting nationalism and democracy was in the course of time given to new leaders from a region beyond the mountains, peopled by men and women from all sections and free from those state traditions which ran back to the early days of colonization. The voice of the democratic nationalism nourished in the West was heard when Clay of Kentucky advocated his American system of protection for industries; when Jackson of Tennessee condemned nullification in a ringing proclamation that has taken its place among the great American state papers; and when Lincoln of Illinois, in a fateful hour, called upon a bewildered people to meet the supreme test whether this was a nation destined to survive or to perish. And it will be remembered that Lincoln's party chose for its banner that earlier device--Republican--which Jefferson had made a sign of power. The "rail splitter" from Illinois united the nationalism of Hamilton with the democracy of Jefferson, and his appeal was clothed in the simple language of the people, not in the sonorous rhetoric which Webster learned in the schools.`;

let words = text.split(" ");
const word = "rhetoric";

words = insertSort(words);

let start = new Date().getTime();
let position = seqSearch(words, word); 
let stop = new Date().getTime();
let elapsed = stop - start; 
if (position >= 0) {
   print("Found " + word + " at position " + position + ".");
   print("Sequential search took " + elapsed + " milliseconds.");
} else {
    print(word + " is not in the file.");
}


/**
position = seqSearch(words, word)일 경우
Found rhetoric at position 190.
Sequential search took 1 milliseconds.

position = binarySearch(words, word)일 경우
Found rhetoric at position 136.
VM48:2 Sequential search took 0 milliseconds.
*/

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9