Binary Search

Binary Search(이진 탐색)은 정렬된 배열에서만 효과가 좋고, 분류되지 않았을때는 쓸모가 없다.

 

console.log(binarySearch([1, 2, 3, 4, 5], 2)); // 1
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5], 6)); // -1
console.log(binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 10)); // 2
console.log(binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 95)); // 16
console.log(binarySearch([5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 100)); // -1

function binarySearch(arr, num) {
  let lowIdx = 0;
  let highIdx = arr.length - 1;
  let midIdx = Math.ceil((highIdx + lowIdx) / 2);

  if (arr[highIdx] < num || arr[lowIdx] > num) return -1;

  while (num !== arr[[midIdx]]) {
    if (lowIdx > highIdx) return -1;
    if (num > arr[midIdx]) {
      lowIdx = midIdx + 1;
    } else if (num < arr[midIdx]) {
      highIdx = midIdx - 1;
    }
    midIdx = Math.ceil((highIdx + lowIdx) / 2);
  }
  return midIdx;
}


// UDEMY

// Original Solution
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

// Refactored Version
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)

 

Big O

Worst and Average : O(log n)

Best : O(1)