recursion_06.순차탐색

Jun 27th 2020 by jyoon

Algorithm

recursion

문제

주어진 배열 요소가 몇번째 인지 확인(순차탐색)
해결방법이 두가지가 있다.
- 첫번재 : recursion
- 두번째 : binary search와 비슷한 방법
- 세번째 : 배열 순회

중요

매개변수를 명시화 하자 !
- recursion 함수 매개변수 선언할때 처음 호출하는 상황말고 자기 자신을 호출하는 상황에서의 매개변수를 생각해야 한다 .
- 그래서 아래와 같은 예제에서 begin, end가 추가가 된것이다.
- 예를 들어 permutation(순열-모든문자열의 조합) 알고리즘을 확인해보자

해결 방법1

POINT1: 이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다.
- 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.
POINT2: 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.
POINT3: return searchRecursion(arr, 0, end-1, target); 이렇게 호출해도 된다.

CODE1

// 2. 매개변수의 명시화(recursion)
// POINT1
function searchRecursion(arr, begin, end, target) {
  if (begin > end) {
    return false
  } else if (target === arr[begin]) {
    return begin
  } else {
    return searchRecursion(arr, begin + 1, end, target)
    // return searchRecursion(arr, 0, end-1, target);  // POINT3
  }
}

// POINT2
console.log(searchRecursion(arr, 0, arr.length-1, 4))

해결 방법2

배열 begin, end 사이에서 바능로 나눠 앞쪽에서 찾고 없으면 뒤에서 찾는 방법
POINT1: 반으로 나눴을 때 왼쪽 탐색
POINT2: 반으로 나눴을 때 오른쪽

CODE2

function search(arr, begin, end, target) {
  if (begin > end) {
    return false
  } else {
    // POINT1: 반으로 나눴을 때 왼쪽 탐색
    var middle = Math.floor((begin + end) / 2)
    if (arr[middle] === target) {
      return middle
    }

    var index = search(arr, begin, middle - 1, target)

    // POINT2: 반으로 나눴을 때 오른쪽
    if (index != false) {
      return index
    } else {
      return search(arr, middle + 1, end, target)
    }
  }
}

var arr = [1, 2, 3, 4, 5]
console.log(search(arr, 0, arr.length-1, 5))

해결 방법3

배열을 순회하면서 찾는다.

CODE3

// 1.배열 사용
var arr = [1, 2, 3, 4, 5]
function search(arr, n, target) {
  for (var i = 0; i < n; i++) {
    if (arr[i] === target) {
      return i
    }
  }
  return false
}

console.log(search(arr, arr.length, 4))