[알고리즘-JS] 이분 검색

문제

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

 

입력 예제

8 32

23 87 65 12 57 32 99 81

 

출력 예제

3

 

 

 

풀이

반 씩 나눠가면서 탐색한다.

 

function solution(target, arr) {
  let answer = 0;
  let lt = 0;
  let rt = arr.length - 1;
  
  arr.sort((a, b) => a - b);
  
  while(lt <= rt) {
    let mid = parseInt((rt+lt)/2);
    if(arr[mid] === target) {
      answer = mid + 1;
      break;
    }
    // target이 mid을 기준으로 왼쪽에 있을 때 rt를 mid 바로 앞으로 옮기기
    else if (arr[mid] > target) rt = mid-1;
    // target이 mid를 기준으로 오른쪽에 있을 때 lt를 mid 바로 뒤로 옮기기
    else lt = mid+1;
  }
  
  return answer;
}