본문 바로가기

Javascript/DSA

Search Algorithm

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