Search Algorithms

Linear Search

주어진 배열에서 어떤 특정 요소를 찾아서 배열의 인덱스를 리턴해라, 만약 값이 없다면 -1을 리턴해라

function func(arr, num) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === num) {
      return i
    }
  }
  return -1
}

function func(arr, num) {
  return arr.findIndex(idx => idx === num)
}

 

* 여기서 forEach를 사용해서 중간에 인덱스를 찾아 return을 하게 되더라도 그 콜백함수의 반환값이 func 함수의 반환값이 되지 않기 때문에 마지막 리턴값을 내보내게 된다 --> 따라서 올바른 인덱스가 아니라 모든 경우에 -1을 반환한다. 그래서 사용하면 안 됨!

 

얘의 Big O는 O(n) 

 

Binary Search

이진 탐색: 정렬이 된 배열에 사용할 수 있는 방법임. 

중앙값을 비교한 후에 크거나 작거나 혹은 같다 라는 것을 이용해서 target 숫자를 찾아내는 방법이다.

function func(arr, target) {
	let left = 0;
    let right = arr.length - 1
    
    while (left <= right) {
    	let mid = Math.floor((left + right) / 2)
        if (arr[mid] === target) return mid
        if (target < arr[mid]) {
        	right = mid - 1
        } else {
        	left = mid + 1
        }
    }
    
    return -1
}

 

얘의 Big O는 O(logn) : 반복될 때마다 절반씩 줄어들기 때문에 O(n) 아님!

 

Recursive Binary Search

function func(arr, target) {
  return search(arr, target, 0, arr.length - 1)
}

function search(arr, target, left, right) {
  if (left > right) return -1

  let mid = Math.floor((left + right) / 2)
  if (target === arr[mid]) return mid
  if (target < arr[mid]) return search(arr, target, left, mid - 1)
  else return search(arr, target, mid + 1, right)
}

 

얘의 Big O는 동일하게 O(logn)