binary search

주 원리 : 현재 머물러있는 합리적 추측 범위를 계속 파악하는 것.

O(log n)번 만에 인덱스를 찾을 수 있다.
최대 log n번의 탐색이 필요하다는 뜻이며, 로그 시간이라고 부른다.
이진 탐색은 매우 빠른 속도로 데이터를 찾을 수 있지만, 반드시 데이터가 정렬되어 있어야 한다.

예시) 추측게임

매 회마다 추측값 한 개를 선택해서 바로 전에 나온 합리적 추측 범위를 둘로 나누어 비슷한 크기의 범위가 두 개 나오도록 한다.

단계별로 나타낸 추측 게임

min = 1min=1m, i, n, equals, 1, max = nmax=nm, a, x, equals, n으로 둡니다.

maxmaxm, a, x 와 minminm, i, n의 평균을 구하되, 정수가 되도록 내림합니다.

추측이 맞으면 끝냅니다. 숫자를 찾았습니다!

추측값이 너무 작으면 minminm, i, n을 추측값보다 1 크게 설정합니다.

추측값이 너무 크면 maxmaxm, a, x를 1 작게 설정합니다.

2 단계로 돌아갑니다.

선형검색

인덱스 0에서부터 순서대로 모든 인덱스를 살펴보는 것

O(n)번 만에 인덱스를 찾을 수 있다.
초대 n번의 탐색이 필요하며, 선형시간이 걸린다.

의사코드 pseudo-code

프로그래밍 언어의 특징과 글을 혼합하여 표현하는 것

추측게임을 의사코드로 표현하기

배열 안에서 검색이 가능하도록 수정된 이진 검색 의사코드 입력값은 array라고 부르는 배열, array의 요소의 개수 n, 검색 대상의 수 target 결과값은 array 속 target의 인덱스 값입니다.

min = 0 이고 max = n-1이라고 합니다.

guess의 값은 max와 min의 평균값을 정수가 되도록 버림한 값입니다.

array[guess]의 값이 target과 같다면 검색을 멈춥니다. 타겟을 찾았습니다. guess를 결과값으로 반환합니다.

추측값이 더 작다면 즉, array[guess] < target이라면, min = guess + 1으로 바꿉니다.

아니면 추측값이 더 큽니다. 그러면 max = guess - 1로 바꿉니다.

2 단계로 돌아갑니다.

위의 의사코드는 array에 찾는 값이 존재하지 않을 경우에 대한 처리 방법이 없다. 따라서 1번 다음에 max값이 min보다 작게 나오면 탐색을 중단하는 코드를 넣어야한다.

max < min이면 검색을 멈춥니다: target이 array에 존재하지 않습니다. -1을 반환합니다.

추측게임 자바스크립트로 구현하기

모든 인덱스를 탐색해야하는 것이 아니라서 for루프 보다는 while이 낫다.

/* Returns either the index of the location in the array,
  or -1 if the array did not contain the targetValue */
var doSearch = function (array, targetValue) {
  var min = 0;
  var max = array.length - 1;
  var guess;
  var count = 0;

  while (max >= min) {
    guess = Math.floor((max + min) / 2);
    println(guess);
    count++;
    if (array[guess] === targetValue) {
      println(count);
      return guess;
    } else if (array[guess] < targetValue) {
      min = guess + 1;
    } else {
      max = guess - 1;
    }
  }
  return -1;
};

var primes = [
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
];

var result = doSearch(primes, 73);
println("Found prime at index " + result);

Program.assertEqual(doSearch(primes, 73), 20);

알고리즘 - 이진탐색

이진탐색에 대해서