문제

merge 정렬

해결 방법1

POINT1: 배열에서 절반을 나누고 절반 index에 해당하는 요소가 target 요소와 비교해서 배열의 왼쪽, 오른쪽을 검색할 것인지 정한다.
POINT2: POINT1 과정을 recursion 한다.

중요

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

CODE1

function binarySearch(items, target, begin, end) {
  if (begin > end) {
    return false
  } else {
    var middle = Math.floor((begin + end) / 2)
    // POINT1
    var compResult =
      target === items[middle] ? 0 : target > items[middle] ? 1 : -1
    if (compResult == 0) {
      return middle
    } else if (compResult < 0) {
      // POINT2
      return binarySearch(items, target, begin, middle - 1)
    } else {
      // POINT2
      return binarySearch(items, target, middle + 1, end)
    }
  }
}

console.log(binarySearch([1, 2, 3, 4, 5], 4, 0, 4))

recursion_08.binarySearch

문제

해결 방법1

중요

CODE1

Code Blog