About Search Algorithm
정렬 알고리즘에서 정렬은 결국 검색을 하기 위한 것이다 라는 이야기를 했었다.
리스트에서는 순차 검색(sequential search) 와 이진 검색(binary search)으로
데이터를 검색할수 있다.
sequential search
순차 검색은 다른말로 선형 검색(linear search) 라고도 한다.
순차 검색은 무작위적인 검색 기법으로 상황에 따라 자료구조의 모든 요소를
검색해야 하는 상황이 발생할 수 있다.
function seqSearch(arr, data) {
return arr.indexOf(data) === -1? false : arr.indexOf(data);
}
function dispArr(search) {
let nums = new Array(100).fill(1).map((x,i) => x+=i).sort(() => .5 - Math.random()),
index = seqSearch(nums, search),
result;
if (index) {
result = ['!!', nums[index], '!!'];
console.log(`${search} is in the array .! result index num : ${index}
${nums.slice(0,index).concat(result, nums.slice(index+3, nums.length)) }`);
}
else {
console.log(`${search} is not in the array .!`);
}
}
// 최소값과 최대값
function seqMinMax(target) {
let nums = new Array(100).fill(1).map((x,i) => x+=i).sort(() => .5 - Math.random()),
value = nums[0], qul, i;
if (target === 'min') {
for (i = 0,len = nums.length; i < len; i+=1) {
if (value > nums[i]) {
value = nums[i];
}
}
}
else if (target === 'max') {
for (i = 0,len = nums.length; i < len; i+=1) {
if (value < nums[i]) {
value = nums[i];
}
}
}
return `${target} result : ${value}`;
}
binary search
이진 검색은 데이터가 이미 정렬이 되어있는 상태에서 검색이 진행 되어야 한다.
예시 코드는 숫자 1~100을 순차적으로 배열에 담고 60을 찾고 있다.
function binSearch(arr, data) {
let upperBound = arr.length - 1,
lowerBound = 0,
count = 0;
while (lowerBound <= upperBound) {
var mid = Math.floor((upperBound + lowerBound) / 2);
console.log(`Up =>${upperBound} Down =>${lowerBound} Mid =>${mid}`);
count++;
if (arr[mid] < data) {
lowerBound = mid + 1;
}
else if (arr[mid] > data) {
upperBound = mid - 1;
}
else {
return mid,count;
}
}
return -1;
}
let nums = new Array(100).fill(0).map((x,i) => x + i + 1);
binSearch(nums, 60)
'Javascript > DSA' 카테고리의 다른 글
DSA end (0) | 2016.09.15 |
---|---|
Set Data Structure (0) | 2016.09.15 |
Dynamic Programming & Greedy Algorithms (0) | 2016.09.11 |
Sorting Data Structure (0) | 2016.08.31 |
Graph Data Structure (0) | 2016.08.31 |