- 이진탐색이란

이진 탐색이란 정렬 되어있는 데이터에서 탐색 범위를 절반씩 좁혀가며 찾고 싶은 타겟 데이터를 찾는 방식이다.

시간복잡도는 O(logN)이다.

위의 사진을 예로 들어서 12를 찾고 싶다고 가정해보자.

이진탐색에서는 시작점과 끝점 총 2개의 탐색범위를 제공한다.

index 0과, 끝점인 index 9의 중간지점인 index 4 (4.5)

index 4는 8이니 8을 새로운 시작점으로 두고 다시 탐색하면 된다.

이진탐색은 매우 넓은 탐색 범위에서, 최적의 해를 찾아야하는 경우에 유용하게 사용할수 있다.

- 재귀의 방법으로 이진탐색 구현

function binarySearch(arr, target, startIndex, endIndex) {
  if (startIndex > endIndex) {
    return -1;
  }

  let midIndex = Math.floor((endIndex + startIndex) / 2);

  // 타겟을 찾았다면 해당 인덱스 반환
  if (arr[midIndex] === target) {
    return midIndex;
  }
  // 중간 값이 찾고싶은 데이터보다 큰 경우 왼쪽부분 다시 탐색
  else if (arr[midIndex] > target) {
    return binarySearch(arr, target, startIndex, midIndex - 1);
  }
  // 중간 값이 찾고 싶은 데이터보다 작다면, 오른쪽 부분 다시 탐색
  else if (arr[midIndex] < target) {
    return binarySearch(arr, target, midIndex + 1, endIndex);
  }
}

let n = 10;

let target = 7;

let arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

let result = binarySearch(arr, target, 0, n - 1);

if (result === -1) {
  console.log("원소가 존재하지 않습니다.");
} else {
  console.log(`${result + 1}번째 값입니다`);
}

- 반복문의 방법으로 이진탐색 구현

function binarySearch(arr, target, startIndex, endIndex) {
  while (start <= end) {
    let mid = Math.floor(endIndex / startIndex);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] > target) {
      endIndex = mid - 1;
    } else if (arr[mid] < target) {
      startIndex = mid + 1;
    }
  }

  return -1;
}

- 상한선과 하한선 함수

let arr = [3, 4, 5, 5, 5, 7, 9];


lowerBound(arr, 5);
upperBound(arr, 5);

즉 lowerBound는 정렬된 배열에서 중복된 값들이 있을때, 가장 왼쪽 인덱스, 즉 가장 작은 인덱스에 존재하는 값을 반환하고,

upperBound는 가장 오른쪽에 있는 인덱스 값을 반환한다.

let arr = [3, 4, 5, 5, 5, 7, 9];

lowerBound(arr, 5, 0, arr.length);
upperBound(arr, 5, 0, arr.length);

function lowerBound(arr, target, startIndex, endIndex) {
  while (startIndex < endIndex) {
    let midIndex = Math.floor((end + start) / 2);

    // 만약 중간 값이 타겟 값보다 크다면
    if (arr[midIndex] >= target) {
      // 최대한 왼쪽으로 이동
      endIndex = midIndex;
    } else {
      // 시작 인덱스를 중간으로 땡겨오기
      startIndex = midIndex + 1;
    }
  }

  return endIndex;
}

function upperBound(arr, target, startIndex, endIndex) {
  while (startIndex < endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] > target) {
      endIndex = midIndex;
    } else {
      startIndex = midIndex + 1;
    }
  }

  return endIndex;
}

function countByRange(arr, leftValue, rightValue) {
  let rightIndex = upperBound(arr, rightValue, 0, arr.length);
  let leftIndex = lowerBound(arr, leftValue, 0, arr.length);

  return rightIndex - leftIndex;
}

console.log(countByRange(arr, 4, 4));

console.log(countByRange(arr, -1, 3));

이런식으로 upperBound와 lowerBound의 함수를 조합해서 해당 범위내에 있는 숫자의 갯수를 구해줄수도 있다.