이분탐색

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.(단 중복값은 존재하지 않습니다)

 

코드

function solution(target, arr) {
  let answer = 0;
  arr.sort((a, b) => {return a - b});
  let mid = Math.floor(arr.length/2);

  while(mid !== 0) {
    if(target === arr[mid]) {
      answer = mid + 1;
      break;
    } else {
      mid = Math.floor(mid/2);
    }
  }
  return answer;
}

let arr = [23, 87, 65, 12, 57, 32, 99, 81]
console.log(solution(32, arr));

 

오답

이 문제에서는 처음 mid 값이 target 값보다 컸기 때문에 전체 배열의 길이의 반으로 쪼개서 왼쪽 구간을 탐색하는 위 방법으로풀렸지만 만약 mid값이 target 값보다 작은 경우에는 오른쪽 구간을 탐색해야 하기 때문에 위의 풀이는 옳지 못하다.

---

이분 탐색(Binary Search)

• 이분 탐색의 주요 조건: 찾고자 하는 데이터가 저장된 배열은 정렬되어 있어야 함
• 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 대소 비교
• 대소 비교 후, 탐색 범위를 절반씩 줄여가며 찾아감

코드

function solution(target, arr) {
  let answer = 0;
  arr.sort((a, b) => {return a - b});
  let lt = 0; //왼쪽 구간
  let rt = arr.length - 1; //오른쪽 구간

  while(lt <= rt) { 
    let mid = Math.floor((lt + rt)/2);
    if(arr[mid] === target) {
      answer = mid + 1;
      break;
    }
    else if(arr[mid] > target) rt = mid - 1; //중간값이 target 값보다 클 경우_오른쪽 구간을 더 이상 확인할 필요가 없음
    else lt = mid + 1; //중간값이 target 값보다 작을 경우_왼쪽 구간을 더 이상 확인할 필요가 없음
  }
  return answer;
}

let arr = [23, 87, 65, 12, 57, 32, 99, 81]
console.log(solution(32, arr));