위코드 코드카타를 정리한 내용입니다.

선형탐색은 반복문을 통해 배열의 요소를 하나씩 확인하며 해당하는 값의 Index 을 구합니다. 이 때 배열의 길이가 길어지고 복잡한 계산이 들어있다면 실행 속도가 느려질 수 있습니다. 그래서 더 효과적인 탐색을 위해 이진 탐색법을 사용합니다. 이진 탐색은 처음부터 끝까지가 아니라 중간을 기준으로 전후를 비교하며 찾는 방법입니다. (선형탐색이나 이진탐색의 요소가 오른차순 혹은 내림차순으로 정렬되어 있어야 함)

문제

오름차순 숫자인 nums 배열과 찾아야 할 target 인자를 받아 target 이 몇 번째 index 인지 리턴합니다.

// input 
nums = [-1,0,3,5,9,12]
target = 9

// output
4 

풀이

중간 지점을 선정하기 위해 low, high 변수를 선언하고, while 반복문을 통해 target 이 배열의 중간값과 같을 때까지 반복문을 실행합니다. 첫번째 조건에 부합하지 않으면 low 와 high 값을 수정하면서 중간값 기준으로 앞과 뒤로 탐색 영역을 좁혀 나갑니다.

let a = [-1,0,3,5,9,12];
let b = 3;

const search = (nums, target) => {
  let low = 0;  
  let high = nums.length-1;

  while(low <= high) { 
    let mid = Math.floor((low+high)/2); // 배열의 중간지점 인덱스 값을 구함

    if(target === nums[mid]) { // 타겟과 중간지점 값을 비교해서
      return mid;  // 같다면 해당 인덱스를 반환
    } else if (target > nums[mid]) { // 타겟이 중간지점보다 뒤에 있다면
      low = mid+1; // 탐색의 시작점을 중간 이후로 잡고
    } else if (target < nums[mid]) { // 타겟이 중간지점보다 앞에 있다면
      high = mid-1;  // 탐색의 마지막 지점을 중간 이전으로 잡는다.
    }
  }
  return undefined;
}

console.log(search(a, b));