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

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

이진탐색

  • 정의
    • 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 것.
    • 오름차순으로 정렬된 리스트일 경우에만 사용할 수 있다는 단점이 있지만, 절반씩 줄여가며 탐색하기 때문에 매우 빠르다.
  • 구현
    • 해당 배열에서 가운데 값을 찾고, 그 값과 비교하여 해당 인덱스에서의 배열의 값이 찾는 값 보다 클때는 앞쪽에서 찾고, 작을때는 뒤쪽에서 찾으면 된다.
    • 코드
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      // 해당 인덱스를 출력해주는 알고리즘 입니다.
      binarSearch = (data, value) => {
      let start = data[0], end = data.slice(-1)[0], index = 0, last = data.length-1
      if (value < start || value > end)
      return -1;
      while (index <= last) {
      let center = parseInt((index+last) / 2)
      if (data[center] === value)
      return center;
      else if(data[center] > value)
      // 해당 인덱스의 배열값이 더 크기때문에 최대 인덱스를 줄인다.
      last = center - 1
      else
      // 해당 인덱스의 배열값이 더 작기때문에 최소 인덱스를 늘린다.
      index = center + 1
      }
      }

      // 호출
      binarSearch([1,5,7,11,25],25) // 4
      binarSearch([1,5,7,11,14,16,18,25],18) // 6

참고자료

댓글

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×