이진 탐색 (Binary Search)

이진탐색이란 이미 정렬되어 있는 배열에서
좌측과 우측 기준점을 잡고, 그 중간 점을 이용해 절반씩 탐색 범위를 좁혀가며 특정 값을 찾는 알고리즘입니다.

배열 내 어딘가에 있는 값을 지정하여 배열의 중간 값과 비교하고 동일하지 않다면 특정 값이 존재할 수 없는 범위를 제거하고

찾고자 하는 값이 있는 범위를 좁혀나가며 결국 찾고자 하는 값을 찾아낼 수 있습니다.

이진탐색은 배열을 순회하며 특정 값을 찾는 알고리즘보다 시간복잡도에서 큰 우위를 점하기 때문에 배열의 크기가 큰 경우 이진 탐색 알고리즘을 사용하여 효과적으로 문제를 해결할 수 있습니다.

간단한 코드로 살펴보자면 아래와 같습니다.

function binarySearch(arr, target) {

  let left = 0;
  let right = arr.length-1;
  let mid;
  
  while(left<=right){
  
  mid = parseInt((left+right)/2)
  
  if(target === arr[mid]){
    return mid;
  } else{
    if(target<arr[mid]){
      right = mid-1
    }
    else{
      left = mid+1
    }
  }
  }
  return -1

};

일반적으로 변수는 총 3개의 변수를 사용합니다.

• 검색 범위의 최소 범위를 담는 left 변수(혹은 start)
• 검색 범위의 최대 범위를 담는 right 변수(혹은 end)
• 특정 값이 담기는 mid 변수

최소 범위와 최대 범위의 순서가 어긋나게 된다면 반복문을 종료하고
그렇지 않다면 특정 값을 찾기위해 검색을 계속 해나갑니다.

반복할 때 마다 검색 범위를 절반씩 줄여나갑니다.

중간 값 ( mid ) 값보다 찾고자하는 값이 크다면
중간 값보다 작은 수는 더 이상 범위에 들어올 수 없기 때문에 left의 값은 mid + 1이 되고

중간 값 ( mid ) 값보다 찾고자하는 값이 작다면
중간 값보다 큰 수는 더 이상 범위에 들어올 수 없기 때문에 right의 값은 mid -1이 됩니다.

이를 반복하며 값을 찾아내면 해당 값을 리턴하고 찾지못하였다면 -1을 리턴하며
이진탐색은 마무리됩니다.

실제로 이진탐색을 사용해야하는 문제가 코딩 테스트나 백준 및 프로그래머스와 같은 사이트에서
출제된다면 파라메트릭 서치와 함께 출제되는 경우가 많습니다.
( 이코테 나동빈님께서 그러셨어요 )

파라메트릭 서치란 ?

최적화 문제를 결정 문제로 바꾸어 해결하는 기법을 의미합니다.

최적화 문제란 어떠한 함수의 값을 최대한 높이거나 최대한 줄이거나 하는 문제를 의미합니다.
특정 범위를 만족하는 최대 값은 무엇인가? 와 같이 말입니다.

이런 최적화 문제를 바로 해결하기 어려운 경우 파라메트릭 서치를 활용해볼 수 있습니다.
최적화 문제를 여러번의 결정 문제( 예 혹은 아니오)로 바꾸어서 문제를 해결하는 것으로 말이죠.

마치며

이진탐색은 선형탐색보다 시간복잡도에서 큰 우위를 점하기 때문에
문제에서 주어지는 탐색 범위가 크다면 이진탐색을 떠올릴 수 있어야 한다고 합니다.

하지만 저는 아직이에요.

파라메트릭 서치와 이분 탐색을 사용한 문제 풀이가 궁금하시다면 아래 링크를 눌러주세용 😃

https://velog.io/@qltkd5959/JS-%EB%96%A1%EB%B3%B6%EC%9D%B4-%EB%96%A1-%EB%A7%8C%EB%93%A4%EA%B8%B0