Toy#10 binarySearch

質問する

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

注意事項

に答える

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를 바로 리턴
*/