알고리즘 이진검색

문제

1. min = 0 이고 max = n-1 입니다.
2.max < min, 이라면 멈춥니다. 타겟이 배열에 존재하지 않습니다. -1을 반환합니다.
3. 'guess'를 'max'와 'min'의 평균으로 계산하고 (정수가 될 수 있도록) 내림합니다.
4. 배열[guess]가 타겟과 같다면 멈춥니다. 찾았습니다! guess를 반환합니다.
5. 만약 추측이 너무 낮았다면, 즉 배열[guess] < 타켓이라면, min = guess + 1로 바꿉니다.
6. 그렇지 않다면 추측이 너무 높습니다. max = guess - 1로 바꿉니다.
7. 2단계로 돌아갑니다.

풀이

var doSearch = function(array, targetValue) {

    var min = 0;

  var max = array.length - 1; // 첫 번째 인덱스는 1이 아니라 0에서 시작합니다.

  var guess;

  var targetValue;

  var count = 0; //count 변수를 0으로 초기화시킵니다.

  while(max >= min){ //max 값이 min보다 커야 반복문이 실행됩니다.

      guess = Math.floor(( max + min )/2); // 받은 인자에 Math.floor 함수를 써서 가운데 인덱스 값의 소수점을 버릴거에요.

      println(guess); // 각 단계의 guess를 출력하게 할래요.

      count++; // 반복문이 실행될 때마다 카운트를 1회씩 증가시킵니다.

      if(array[guess] < targetValue){ // 우리가 추론한 guess 값이 targetValue보다 작을 경우,

          min = guess+1;  //범위를 하나씩 더 늘립니다.

      }

      else if(array[guess]> targetValue){ //우리가 추론한 guess 값이 targetValue보다 클 경우,

          max = guess-1; // 범위를 하나씩 더늘립니다.

      }

      else { //추론한 guess 값이 targetValue와 일치하다면

          println(count); // 마지막 반복문에서 최종 카운트된 횟수를 출력합니다.

      return guess; // guess를 반환합니다.

      }

    }  

    return -1; // 배열에 targetValue가 없을 경우, -1을 반환합니다. 즉 max < min이면 더이상 반복문을 돌리지 않습니다.

};

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);
Program.assertEqual(doSearch(primes, 89), 23); // 다른 수도 검사해볼까요?
Program.assertEqual(doSearch(primes, 13), 5);  // 다른 수도 검사해볼까요?

* reference

• https://ko.khanacademy.org