이진탐색(binary search)_반복문과 재귀함수를 통한 풀이

이진탐색 알고리즘은 특정 값이나 인덱스를 탐색해야 할 때 걸리는 시간이나 메모리를 줄이기 위해 사용하는 알고리즘 방법이다.

Q. 오름차순 정렬된 정수의 배열 (arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

해당 문제는 반복문과 제귀함수를 통해 구현할 수 있다.
먼저 반복문을 통해서 구현해본 코드이다.

//반복문으로 구현했을 때
const binarySearch = function (arr, target) {
  let start = 0
  let end = arr.length -1
  let mid


  while (end - start >= 0) {
    mid = parseInt((start + end) / 2)

    if(arr[mid] === target)
      return mid
    else if(arr[mid] > target)
      end = mid - 1
    else if(arr[mid] < target)
      start = mid + 1
  }
  return -1
};

while 문의 조건을 end가 start보다 클 때로 설정해놓고
mid는 start와 end의 중간(/2)으로 한다.

이제 조건문으로 값을 찾아주면 되는데, mid의 인덱스 값이 찾는 값과 같다면 인덱스를 리턴해준다.
( 중간 값이 찾는 값이기 때문)
그게 아니라면 end값을 줄여주고, start값을 늘려가며 중간 값을 탐색한다.

반복문이 종료되었는데도 값을 찾지 못한다면 찾는 값이 없는 것이기 때문에 -1을 리턴해준다.

console.log를 찍은 결과를 보면 더 쉽게 이해할 수 있다.

 재귀함수로 해결한 코드이다.

//재귀함수
const binarySearch = function (arr, target) {
  let startPoint = 0
  let endPoint = arr.length -1
  let midPoint = Math.floor((startPoint + endPoint) / 2)

  const binary = (start, mid, end) => {
    if(end < start)
      return -1
    mid = Math.floor((start + end) / 2)

    if(arr[mid] === target)
      return mid
    else if(arr[mid] > target)
      return binary(start, mid, mid-1)
    else if(arr[mid] < target)
      return binary(mid+1, mid, end)
  }
  return binary(startPoint, midPoint, endPoint)
}

위와 크게 다르지 않은 방법이지만 재귀함수를 이용했기 때문에 초기값, 재귀 안에서 호출되는 값을 각각 정의해줬다.

위는 배열이 이미 오름차순으로 정의되어 있고,  배열이 하나라서 빠른 이해가 가능했지만 두 개의 배열일 때의 문제는 해결 하지 못했다..
이 경우도 해결해서 곧 포스팅해야겠다.

이진 탐색(Binary Search) 알고리즘

이미 정렬되어 있는 배열에서 탐색 범위를 두 부분으로 나눠 절반씩 좁혀가며 필요한 부분에서만 탐색하도록 하는 방법

1

2

3

4

5

6

7

8

9

10

간단하게 up/down게임으로 값을 찾아내는 것이라고 생각하면 이해하기 쉽다.

위 배열에서 내가 찾는 값이 7이라고 할 때

1. 먼저 중간 값인 5와 비교한다 (5 < 7)
2. 찾는 값이 더 크므로 5과 10의 중간값인 8과 비교한다 (7 < 8)
3. 찾는 값이 더 작으므로 6과 8의 중간값인 7과 비교한다.
4. 찾는 값과 일치하므로 종료

이진 탐색을 하기 위한 선행조건은 배열의 값이 정렬되어 있어야 비교가 가능하다.