[JS] 순차검색

1. 순차 검색

 순차 검색은 가장 쉽고 단순한 검색 방법으로써, 순서대로 항목을 비교하면서 검색하는 순차 검색과 인덱스 테이블을 사용하여 검색의 효율성을 높인 색인 순차검색이 있다.

 

 

 정렬되지 않은 순차 자료구조에서의 순차검색

  

  첫 번째 원소부터 시작해서 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다. 키 값이 일치하는 원소를 찾

 으면 그 원소가 몇 번째 원소인지를 반화한다. 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 검색이 실패된다.

 

 

 

 

   순차 검색에서 비교횟수는 원소의 위치에 따라 다르다. 찾고자 하는 원소가 첫 번째 원소면 비교횟수는 1이고, 마지막 원소라면 비교횟    수가 n이다. 따라서 순차 검색의 평균 시간 복잡도는 O(n)이다.

 

 

 정렬되어 있는 순차 자료구조에서의 순차 검색

 

 정렬되지 않은 자료에서 순차검색을 하는 경우, 마지막 원소까지 비교를 한 후에 실패여부를 알 수 있지만, 자료를 미리 정렬했을 때는 다르다. 왜냐하면 찾는 키 값이 원소의 키 값보다 크면 원소가 없는 것으로 판단하여 더이상 검색을 수행하지않고 끝낼 수 있기 때문이다.

 

   비교횟수는 정렬되지 않은 순차자료구조를 검색할 때 보다 최대 반으로 줄어든다. 하지만 평균 복잡도는 똑같이 O(n)이다.

 

 

2. 색인 순차 검색

 색인 순차 검색은 인덱스 테이블을 추가로 사용하여 탐색의 효율을 높인 검색 방법이다. 인덱스 테이블은 배열에 정렬되어 있는 자료 중에서 일정한 간격으로 떨어져 있는 원소들을 가지고 있다. 자료가 저장되어 있는 배열의 크기가 n이고, 인덱스 배열의 크기가 m일 때, 배열에서 n/m 간격으로 떨어져 있는 원소의 그의 인덱스를 인덱스 테이블에 저장한다. 찾고자 하는 키 값을 인덱스 테이블에서 검색하여 인덱스 테이블[i] <= 키 값 < 인덱스 테이블[i+1]를 만족하는 i를 찾아서 순차검색을 수행한다.

 

 

 

 위 그림을 보자. 위 그림에서 어떤 사용자가 4를 검색하려고 한다. 먼저, 인덱스 테이블에서 검색을 실시한다. 4는 1보다 크고 5보다 작기 때문에 인덱스 테이블에서는 5의 인덱스 2를 반환한다. 그러면 자료가 저장되어 있는 배열에서 0부터 반환된 인덱스 2번까지를 검색 범위로 정하고 순차검색을 수행하면 된다.  색인 순차 테이블의 성능은 인덱스 테이블 크기에 따라 달라진다. 인덱스 테이블 크기가 줄어들면 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 검색해야 하는 범위도 커진다. 인덱스 테이블의 크기를 늘리면 배열의 인덱스를 저장하는 간격이 작아지므로 배열에서 검색해야 하는 범위는 작아지겠지만, 인덱스 테이블을 검색하는 시간이 늘어나게 된다. 색인 순차 검색의 시간복잡도는 O(m + n/m)이 된다.

 

 

3. 프로그램 코드

// 정렬되지 않은 순차 자료구조에서의 순차 검색
function seqSearch1(key, arr){
  let idx = 0;

  for(; idx<arr.length; idx++){
    if(key === arr[idx])
      break;
  }
  
  return idx < arr.length ? idx : null;
}

// 정렬된 순차 자료구조에서의 순차 검색

function sorted(arr){
  arr.sort((a,b) => a-b);
  return arr;
}

function seqSearch2(key, arr){
  let idx = 0;
  let ischeck = false;
  arr = sorted(arr);
  console.log(arr);

  for(; idx<arr.length; idx++){
    if(key === arr[idx]){
      ischeck = true;
      break;
    }
    else if(key < arr[idx]){
      break;
    }
  }
  
  return ischeck ? idx : null;
}


// 색인 순차 검색
function indexSeqSearch(key, arr){
  arr = sorted(arr);
  const indexTable = createIndexTable(arr);
  let answer = 0;
  let isNone = true;
  let start = 0;
  let end = 1;

  while(start < indexTable.length){
    if(indexTable[start].val <= key && indexTable[end].val > key){
      start = indexTable[start].idx;
      end = indexTable[end].idx;
      isNone = false;
      break;
    }
    start++;
    end++;
  }

  if(isNone)  return null;

  for(let i=start; i<=end; i++)
    if(arr[i] === key){
      answer = key;
      isNone = false;
      break;
    }

  return isNone ? null : answer;
}

function createIndexTable(arr){
  const tLen = parseInt(arr.length/2);
  const indexTable = [];
  let i = 0;

  for(; i<arr.length; i+=tLen){
    indexTable.push({idx: i,val:arr[i]});
  }

  //인덱스 테이블에 첫 번째 값, 마지막 값은 무조건 들어가야 함.
  if(i !== arr.length-1)
    indexTable.push({idx:arr.length-1, val:arr[arr.length-1]});

  return indexTable;
}

 

 

4. 참고 자료

 자바로 배우는 쉬운 자료구조, 한빛 아카데미