Toy#10 binarySearch

문제

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1

주의사항

• 이진탐색 알고리즘(O(logN))을 사용해야 합니다.
• 단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
• target이 없는 경우, -1을 리턴해야 합니다.

풀이

1. 이진탐색 알고리즘

arr = [0, 1, 2, 3, 4, 5, 6]
target = 2

1. 가운데 위치한 임의의 값 3을 선택
   선택한 값 3과 찾고자 하는 값 2를 비교
   2 < 3 이므로 2는 3의 왼쪽에 존재하는 것을 알 수 있음

2. 3을 기준으로 왼쪽에 있는 배열 값들을 대상으로 다시 탐색 진행
   [0, 1, 2]
   가운데 임의의 값 1을 선택
   1 < 2 이므로 2는 1의 오른쪽에 존재하는 것을 알 수 있음

3. 1의 오른쪽 기준으로 배열을 다시 설정해보면 
   [2] 배열에 값이 하나만 남게 되고 값을 확인해 보면
   2 === target 

2. 코드에 적용해 본다면?

const binarySearch = function (arr, target)) {
  let head = 0;
  let tail = arr.length - 1
  let mid;
  
  while(head <= tail){
    mid = Math.floor((head + tail) / 2)
    if(arr[mid] === target) return mid;
    else if(arr[mid] > target) tail = mid - 1;
    else head = mid + 1;
  }
  
  return -1;
}

/*
arr = [0, 1, 2, 3, 4, 5, 6]
target = 2

1. head = 0 / tail = 6
   head <= tail 이므로 while문으로 고고
   mid = 3
   arr[mid] = 3 이니까 target보다 크므로 else if 구문에 걸려서
   tail = 2
   
2. mid = 1
   arr[mid] = 1 이니까 target보다 작으므로 else 구문에 걸려서
   head = 2
   
3. mid = 2
   arr[mid] = 2 이니까 target과 값이 같으므로 인덱스 값을 지닌 mid를 바로 리턴
*/