검색(Search)

검색 : 특정 값을 찾는 일

선형 검색 : 정렬된 값 or 정렬되지 않은값 모두 사용가능한 검색
이진 검색 : 정렬된 값일때 사용가능한 검색

선형 검색

1. 배열의 0번째 인덱스부터 전체를 접근 하여 값을 찾는 검색

2. 시간복잡도 : O(n)

var arr1 = [1,3,5,7,9]
var arr2 = [2,4,6,8,10]

function linearSearch(arr, num) {
  for(var i=0; i<arr.length; i++) {
    if(arr[i] == num) {
      return true
    }
  }
  return false;
}

console.log(linearSearch(arr1, 3)) // true
console.log(linearSearch(arr1, 4)) // false

console.log(linearSearch(arr2, 6)) // true
console.log(linearSearch(arr2, 7)) // false

 

이진 검색

1. 배열의 중간 값을 확인해 큰지 작은지 구분한다

2. 큰 경우 : 중간 값보다 큰 쪽을 검색

3. 작은 경우 : 중간 값보다 작은 쪽을 검색

var arr1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

function binarySearch(arr, num) {
  var lowIndex = 0;
  var highIndex = arr.length;

  while(lowIndex <= highIndex) {
    var midIndex = Math.floor((highIndex+lowIndex)/2);
    console.log(`midIndex : ${midIndex}, lowIndex : ${lowIndex}, highIndex : ${highIndex}`)

    if(arr[midIndex] == num) {
      return midIndex;
    } else if(num>arr[midIndex]) {
      lowIndex = midIndex+1;
    } else {
      highIndex = midIndex-1;
    }
  }
  return -1
}

console.log(binarySearch(arr1, 5))
// midIndex : 8, lowIndex : 0, highIndex : 16
// midIndex : 3, lowIndex : 0, highIndex : 7
// midIndex : 5, lowIndex : 4, highIndex : 7
// midIndex : 4, lowIndex : 4, highIndex : 4
// 4

console.log(binarySearch(arr1, 17))
// midIndex : 8, lowIndex : 0, highIndex : 16
// midIndex : 12, lowIndex : 9, highIndex : 16
// midIndex : 14, lowIndex : 13, highIndex : 16
// midIndex : 15, lowIndex : 15, highIndex : 16
// midIndex : 16, lowIndex : 16, highIndex : 16
// -1