[알고리즘] 이진탐색 정리

 

이진 탐색은 정렬된 매우 큰 범위 내에서 최적의 해를 찾는 경우에 유리하다.
이진탐색 알고리즘은 O(logN)의 복잡도를 보장한다.

---

재귀함수를 이용한 이진탐색

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

let target = 11;

function b_search_recur(arr, target, left, right) {
  let mid = parseInt((left + right) / 2);

  if (left > right) {
    return -1;
  }

  if (arr[mid] == target) {
    return mid;
  } else if (arr[mid] < target) {
    return b_search_recur(arr, target, mid + 1, right);
  } else {
    return b_search_recur(arr, target, left, mid - 1);
  }
}

console.log(b_search_recur(arr, target, 0, arr.length - 1)); //5(index값)

반복문을 이용한 이진탐색

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

---

정렬된 배열에서 특정 원소의 개수 알기

function lowerBound(arr, target, left, right) {
  while (left < right) {
    let mid = parseInt((left + right) / 2);
    if (arr[mid] >= target) right = mid;
    else left = mid + 1;
  }
  return right;
}

function upperBound(arr, target, left, right) {
  while (left < right) {
    let mid = parseInt((left + right) / 2);
    if (arr[mid] > target) right = mid;
    else left = mid + 1;
  }
  return right;
}

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

  return rightIndex - leftIndex;
}

let arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9];

console.log(countByRange(arr, 2, 4)); //7