이진 탐색?

: 이진 탐색은 정열된 자료에서 '중앙값'을 이용해 검색 범위를 줄여나가며 값을 조회하는 알고리즘 방법

이진 탐색 방법

1. 전체 자료에서 중앙에 위치한 값(mid value)을 찾습니다.
   high value = 최댓값 (ex. array.length - 1)
   low value = 최소값 (ex. 0)

mid value = low value + (high value - low value) / 2

2. 만약 search value = mid value면, mid value를 return 해줍니다.
3. 만약 search value > mid value면, 최소값인 low value를 높여 범위를 좁혀준 후, mid value를 다시 찾습니다.

low value = mid value + 1

4. 만약 search value < mid value면, 최댓값인 high value를 낮춰 범위를 줄여준 후 mid value를 다시 찾습니다.

high value = mid value - 1

5. high value = low value가 될 때까지 반복하고, search value가 존재하지 않으면 null 또는 '없음'을 표시할 수 있는 값으로 대체해 반환합니다.

const serachValue = 2;
let midValue = Math.floor(0 + (3 - 0)) / 2  // 1
let highValue = array.length - 1
let lowValue = 0;

while (lowValue !== midValue) {
  if (midValue === searchValue) {
      return 'successfully searched'
  } else if (midValue > searchValue) {
      lowValue = midValue + 1;
      midValue = lowValue + (highValue - lowValue) / 2
  } else if (midValue < searchValue) {
  	highValue = midValue - 1;
    midValue = lowValue + (highValue - lowValue) / 2
  } else {
  	return "have no found serach value"
  }
}

배열 크기가 증가하면 이진 탐색 단계는 몇 개 늘어날까?

만약 search value가 동일하고, 배열의 크기만 늘릴 경우, 배열의 크기가 2배로 늘어날 때마다 최대 이진 탐색 단계는 1씩 증가합니다. 예를 들어 배열의 크기가 3이고 최대 탐색 단계가 2단계라면, 배열의 크기가 2배인 6으로 늘어났을 때는 탐색 단계가 3단계로 1 증가하게 됩니다.