이진탐색 알고리즘

　책자에 나온 것을 참조하면서 보다가, 만약 배열의 검색길이가 유지된 채 루프를 돌린다면 얼마나 많이 돌아갈지 궁금해져서 실험했다.

function binary_search(arr,searchValue){

  let mid = Math.floor(arr.length/2); 
//console.log(mid);

  for(let i=0; i < arr.length; i++){
    if ( arr[mid] === searchValue ) {
      return `값 있음`;
    }
    else if ( arr[mid] > searchValue ) {
         mid = mid-1
    }
    else if ( arr[mid] < searchValue) {
         mid = mid+1
    }
    else { return `찾는 값이 존재하지 않습니다`; } 
  }
}

let arr = [1,2,3,4,5,6,7]
binary_search(arr,5);
> "값 있음"

결과는 잘 나와서 문제가 없어보이겠지만, 내부에서 루프 회전이 엄청 일어나고 있다.

대량의 수를 가진 배열의 경우, 위에 방법으로 하면 검색에 엄청난 시간을 투자한다.

하단 링크 블로그를 참조해서 검사를 진행해봤다.

이진탐색 자바스크립트

function binary_search(arr,searchValue){
  let mid = Math.floor(arr.length/2); 
  
  for(let i=0; i < arr.length; i++){
   // 얼마나 검사하는지 확인하려고 넣었다. 
   console.log(`${i}: mid: ${mid}, data: ${arr[mid]}`);

    if ( arr[mid] === searchValue ) {
      return `값 있음`;
    }
    else if ( arr[mid] > searchValue ) {
         mid = mid-1
    }
    else if ( arr[mid] < searchValue) {
         mid = mid+1
    }
    else { return `찾는 값이 존재하지 않습니다`; } 
  }
}

let arr = [];
for (let i = 1; i <= 240000; i++) {
arr.push(i);
}

1 ~ 240,000까지의 수를 넣은 배열의 경우, binary_search(arr,1200);를 했을 때 118801번이나 회전하고 찾아내었다. (돌리다가 물 뿜었다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ)

책에서는 18번, 윗 분의 방법으로는 12번으로 나와야하는게 맞다고 해서 결국 코드를 제시된 대로 수정했다.

• 처음과 마지막값 추가
• for문에서 while로 변경하면서 조건문 변경

function binary_search(arr,searchValue){

  let low = 0;
  let high = arr.length-1
  //루프 회전 수를 알기 위한 index
  let index = 0;

  while(low <= high){
   let mid = Math.floor((high + low) / 2);

    if ( arr[mid] === searchValue ) {
      return `값 있음`;
    }
    else if ( arr[mid] > searchValue ) {
         //mid = mid-1
         high = mid - 1;
    }
    else if ( arr[mid] < searchValue ) {
        // mid = mid+1
        low = mid+1
    }
    else {  return `찾는 값이 존재하지 않습니다`;  }
    index++;
   //콘솔 찍는용
   console.log(`${index}번 회전 - mid: ${mid}, data: ${arr[mid]}`);

  }
}

　윗분 블로그에도 이진탐색은 순차적으로 정렬된 것이 기준으로 탐색이 된다고 적혀있다.
let arr = [1,10,2,38,29,5,7,8,50,60,87,22]와 같이 임의의 배열을 넣었을 땐, 일정치 않은 순서로 인해 검색이 진행되지 않는 문제점 발생하는 것을 보았고 sort()로 재정렬도 넣었다.

function binary_search(arr,searchValue){

  let sortArr = arr.sort(function(a, b) {
      return a - b;
  });
  console.log(sortArr);
  let low = 0;
  let high = sortArr.length-1
  //루프 회전 수를 알기 위한 index
  let index = 0;

  while(low <= high){
   let mid = Math.floor((high + low) / 2);

    if ( sortArr[mid] === searchValue ) {
      return `값 있음`;
    }
    else if ( sortArr[mid] > searchValue ) {
         //mid = mid-1
         high = mid - 1;
    }
    else if ( sortArr[mid] < searchValue ) {
        // mid = mid+1
        low = mid+1
    }
    else {  return `찾는 값이 존재하지 않습니다`;  }
    index++;
   //콘솔 찍는용
   console.log(`${index}번 회전 - mid: ${mid}, data: ${sortArr[mid]}`);

  }
}