[JavaScript] 이진 탐색(Binary Search) 구현하기

비얌·2023년 1월 16일
Binary Search이진 탐색
1
post-thumbnail

개요

자바스크립트로 이진 탐색(Binary Search)을 구현하는 과제를 받았다.

문제를 풀기에 앞서 이진 탐색에 대해 살펴본 후, 정답과 풀이 과정에 대해 알아보자.

➕ 기존에 포스팅한 코드에 대한 피드백을 받고 수정하였다! 그리고 변경 사항에 대한 설명도 기록했다(열린구간 👉 반열린구간, let 👉 const 등)


문제 설명

과제는 이진 탐색을 구현하는 binarySearch라는 함수를 완성하는 것이다.

binarySearch(array, value)에서 array에는 [1, 2, 3, 4, 5]와 같은 배열이 들어가고, value에는 array에서 찾을 원소가 들어간다. array에서 value를 찾아 그 인덱스를 리턴한다.

만약 value가 array에 없다면 -1을 리턴해야 한다. 

const binarySearch = (array, value) => {
  
	// TODO
  
}

const dataA = [1, 2, 3, 4, 5]
console.log(binarySearch(dataA, 2)) // 1

const dataB = [1, 3, 5, 7, 9, 11, 13, 15, 17]
console.log(binarySearch(dataB, 7)) // 3

const dataC = [1, 3, 5, 7, 9, 11, 13, 15, 17]
console.log(binarySearch(dataC, 4)) // -1

const dataD = [1, 3, 5, 7, 9, 11, 13, 15, 17]
console.log(binarySearch(dataD, 17)) // 8

const dataE = [1, 3, 5, 7, 9, 11, 13, 15, 17]
console.log(binarySearch(dataE, 1)) // 0

const dataF = [1, 2]
console.log(binarySearch(dataF, 1)) // 0

const dataG = [1, 2]
console.log(binarySearch(dataG, 2)) // 1

const dataH = [1, 2, 5]
console.log(binarySearch(dataH, 6)) // -1

이진 탐색(Binary Search)

이진 탐색이란?

앞으로 알아봐야 할 이진 탐색과 기본적인 탐색 알고리즘인 순차 탐색을 비교하여 알아보도록 하자.

순차 탐색(Sequential Search)은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 즉, 모든 데이터를 하나씩 확인한다.

반면에 이진 탐색(Binary Search)이란, 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
(주의: 정렬된 데이터가 아니면 이진 탐색이 불가능하다)

그렇다면 이진 탐색은 순차 탐색에 비해 어떤 장점이 있을까? 이진 탐색은 순차 탐색보다 빠르다는 장점이 있다. 이 빠르기를 정량화하여 나타낼 수 있는데, 이를 시간 복잡도라고 한다. 아래에서 이진 탐색과 순차 탐색의 시간 복잡도에 대해 알아보자.


이진 탐색의 시간 복잡도

시간 복잡도는 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.

복잡도를 표현하기 위해서는 빅오 표기법을 사용한다.
빅오 표기법이란, 컴퓨터 과학에서 일반적으로 알고리즘의 시간복잡도를 나타내는데 사용하는 표기법이다.

이진 탐색의 시간복잡도는 O(logN)으로, 시간 복잡도가 O(n)인 순차 탐색에 비해 빠르다!

  • 순차 탐색(O(n)): 배열에 있는 첫번째 원소부터 n번째 원소까지 하나하나 탐색한다. 따라서 시간 복잡도가 O(n)이 된다.
  • 이진 탐색(O(logN)): 정렬된 배열에서 범위를 반씩 줄여가면서 탐색하므로 시간 복잡도는 O(log2N)이다. (밑이 생략되어 있길래 밑이 10인 상용로그인줄 알았으나, 프로그래밍에서 log의 밑이 생략되어 있으면 2가 생략된 것이라고 한다.)

이진 탐색의 동작 과정은 이 영상에서 자세히 설명하고 있다.


이진 탐색 구현하기

정답

자바스크립트로 이진 탐색을 구현한 결과는 다음과 같다. 풀이한 과정이 길기 때문에 정답을 미리 작성하기로 했다.

const binarySearch = (array, value) => {
  let start = -1; 
  let end = array.length; 
  while (end - start > 1) {
    let mid = Math.floor((end - start) / 2) + start;
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      end = mid;
    } else {
      start = mid;
    }
  }
return -1
}

풀이 과정

이번에도 풀면서 삽질을 많이 했는데, 풀이한 흐름을 포스팅에 담아보려고 한다.

시도 1) start와 end를 정할 생각을 못함

맨 처음에 시도했던 풀이는 아래와 같다. 이때는 start와 end라는 변수를 만들 생각을 못하고 mid라는 변수만 만들었었다.

즉, mid라는 변수로 start와 end를 모두 표현하고자 했다. 하지만 그것은 불가능하다..! 왜냐하면 start와 end가 계속 변화하기 때문이다. 아래의 코드는 루프를 가장 처음 돌 때에만 적용이 가능한 풀이이다.

const binarySearch = (array, value) => {
  나 -처음
  let mid = Math.floor(array.length / 2);
  while () {
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      mid = Math.floor(mid / 2);
    } else {
      mid = mid + Math.floor(mid / 2);
    }
}

시도 2) start와 end를 만들다! 그런데 mid를 활용하지 못하는데...

시도 1에서 많이 고민하다가, start와 end를 만드는 것에 성공했다! binarySearch 함수 본문의 흐름도 나름 잘 짠 것 같다. 

const binarySearch = (array, value) => {
  let start = 0;
  let end = array.length - 1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      end = end - Math.floor(mid / 2);
    } else {
      start = Math.floor(mid / 2);
    }
  }
  return -1
}

💥 하지만!!!! 흐름은 비슷해도 틀린 부분이 많다.

  1. 먼저, mid를 구하는 식이 틀렸다. let mid = Math.floor((start + end) / 2)로는 정확한 mid를 구할 수 없다. 왜냐하면 start가 아래의 else 문에서 변경될 수 있기 때문이다. 따라서 let mid = Math.floor((end - start) / 2) + start라고 하는 것이 옳다.
    👉 아니었음!! let mid = Math.floor((start + end) / 2)라고 해도 된다. 왜냐하면 start와 end가 최신 값으로 계속 바뀌기 때문에 이렇게 써도 문제는 없다. 하지만 보통 이렇게 쓰지는 않는다. 왜냐하면 중간을 구할 때 관습적으로 이렇게 많이 쓰기 때문이고, 또 자바스크립트에서는 아니지만 다른 언어에서 오버플로우가 날 가능성이 있기 때문이다.

  2. else if와 else 부분도 틀렸다. 보면 end와 start가 각각 mid라는 값을 가리키게 하려는 것을 알 수 있다. 그러면 end에 end - Math.floor(mid / 2) 대신 그냥 mid를 대입해주면 된다! start도 Math.floor(mid / 2)가 아니라 단순하게 mid를 대입해주면 된다.
    mid가 let mid = Math.floor((start + end) / 2);에 의해 탐색을 할 때마다 변화한다는 것을 잊고 mid를 변형해서 최신의 mid를 만들려고 한 것 같다. 하지만 mid는 while문 안에서 탐색할 때마다 새롭게 갱신되고 있다는 것을 기억하자!!

  3. 마지막으로 while의 조건이 틀렸다. 나는 단순히 start가 end보다 왼쪽에 있어야 하니 while의 조건에 start <= end라고 쓴 거였는데, 이 부분을 end - start > 1로 바꿔야 한다. 이는 start와 end의 간격이 1 이하가 되면, 즉 start와 end가 붙어 있으면 while문을 종료한다는 뜻이다. 왜냐하면, start와 end 사이의 mid를 가지고 array에 value가 있는지를 판단하면서(array[mid] === value) start와 end 사이의 간격을 좁히는데 start와 end가 붙어 있다면 이미 array[start]와 array[end] 모두가 value가 아니고, 중간에는 값도 없으므로 array에는 value가 없는 것이다.


시도 3) 구현에 성공했다! 하지만 첫 번째와 마지막에 위치한 값을 찾지 못하는데...

위에서 언급한 세 가지를 고쳤다. 하지만, 문제가 있었다. 바로 value가 array에서 첫 번째나 마지막 값이라면 이를 찾지 못한다는 것이었다. 그래서 애초에 start를 1 줄이고, end를 1 늘려서 처음과 마지막 값도 탐색에 포함되도록 했다.

const binarySearch = (array, value) => {
  let start = 0; 
  let end = array.length - 1; 
  while (end - start > 1) {
    let mid = Math.floor((end - start) / 2) + start;
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      end = mid;
    } else {
      start = mid;
    }
  }
  return -1
}

💥 변경한 부분

  1. start = 0 👉 start = -1
  2. end = array.length - 1 👉 end = array.length

시도 4) 성공! 첫 번째와 마지막에 위치한 값도 찾을 수 있다!

start와 end를 변경하여 binarySearch 함수를 완성했다!!

const binarySearch = (array, value) => {
  let start = -1; 
  let end = array.length; 
  while (end - start > 1) {
    let mid = Math.floor((end - start) / 2) + start;
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      end = mid;
    } else {
      start = mid;
    }
  }
  return -1
}

📌 완성된 코드에 관한 피드백

코드가 완성된 듯 싶었지만, 개선할 사항이 있었다! 블로그를 읽은 분이 주신 피드백을 알아보자.

  1. mid를 선언할 때 let mid = Math.floor((end - start) / 2) + start라고 했었다. 하지만 여기서 let 보다 const를 쓰는 것이 낫다. 처음에는 mid가 계속 변화하니까 let을 써야 하는 것이 아닌가? 하고 생각했는데, mid가 변화하는 것이 아니라 while문을 돌면서 mid가 새롭게 계속 선언되는 것이어서 const를 써도 됐다!

  2. 이건 아까도 언급했지만, 꼭 let mid = Math.floor((start + end) / 2)대신 let mid = Math.floor((end - start) / 2) + start라고 하지 않아도 된다. 왜냐하면 start와 end 값이 계속 최신 값으로 바뀌기 때문에 이렇게 해도 답이 나온다. 하지만 이렇게 보통 쓰지 않는 이유는 두 가지가 있는데 첫 번째 관습적으로 이렇게 많이 쓰기 때문이고, 두 번째는 자바스크립트는 아니지만 다른 언어에서 오버플로우가 날 가능성이 있기 때문이다.

  3. 시도 4에서 완성한 풀이에서는 start와 end는 모두 닫힌구간이었다. 하지만 프로그래밍을 할 때에는 반열린구간을 쓰는 것이 좋다고 한다! 그래서 아래의 코드로 수정했다. 변경한 사항에 대한 설명은 아래와 같다.

    const binarySearch = (array, value) => {
  let start = 0; 
  let end = array.length; 
  while (end - start > 0) {
    let mid = Math.floor((end - start) / 2) + start;
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return -1
}
  • 이전에는 start와 end 모두 범위에 포함되지 않는 열린 구간이었다. 하지만 피드백을 받고 end의 위치가 포함되어 닫힌 구간이고, start가 열린 구간으로 start부터 end까지 반열린구간이 되게 수정하였다.
  • 그림으로 그려보면 닫힌구간과 반열린구간인 코드는 아래와 같다.
  • while의 조건문이 end - start > 1에서 end - start > 0로 바뀌어 start와 end의 간격이 1이어도 되게 되었다. 이유는 이전에는 찾으려는 값인 value가 start와 end에 포함이 안되었지만(그래서 찾으려는 값이 start와 end에 있지 않아서 탐색하지 않아도 됨) 이제는 start에서 포함하기 때문에(찾으려는 값이 start에 있을 수 있어서 탐색해야 함) start와 end의 간격이 1이어도 되게 바뀐 것이다.
  • start가 mid에서 mid + 1로 바뀐 이유는 start에 그대로 mid를 대입하면 존재하지 않는 값을 찾을 때 무한루프를 돌 수 있기 때문이다. 예를 들면 10을 찾는다고 할 때, 아래와 같이 mid가 계속 9가 되기 때문에 start가 9에서 머물러 무한루프를 돌게 된다.

🐹 회고

분명히 몇 달 전에 파이썬으로 이진 탐색 알고리즘 문제를 접하고 공부했던 기억이 나는데...!!! 구현하는 법을 정말 완전히 잊어버렸다😂 지금보니 그때 과연 정확히 이해를 한 게 맞을까? 하는 생각이 든다 🤦‍

어쨌든 여러가지 시도를 거쳐 결국 이해해서 다행이다!!

그리고 자바스크립트 코드를 더욱 많이 짜보면서 자바스크립트에 익숙해져야겠다는 다짐을 했다. 처음에 array.length가 아니라 len(array)라고 썼어서 많이 반성했다...

그리고 피드백을 받고 열린구간 닫힌구간을 이해 못해서 엄청 애를 먹었는데...! 그래도 그림을 그려가면서 해보니까 조금 이해가 된 것 같다!!


이진 탐색에서 구간에 관한 고민과 답변이 있는 게시물이다.
https://www.acmicpc.net/board/view/83220

이진 탐색의 구간에 관한 포스팅이다.
https://eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4

profile
비얌
🐹강화하고 싶은 기억을 기록하고 공유하자🐹
이전 포스트

[JavaScript] 값과 변수 이해하기

다음 포스트

2023년 1월 회고

0개의 댓글