[Algorithm] binarySearch(기초)

이진 탐색을 만족하기위해서는
재귀 사용해서 풀어야하는데

하나의 값을 비교할때마다 for문을 사용하면 O(logN)을 만족할 수 없다.

원래의 기존 메서드만 이용해서 값을 구할 수는 있다 하지만.

  return arr.indexOf(target); //해당 인덱스 번호 출력
  //indexOf 자체가 while()문을 이용하기때문에 시간복잡도가 O(N)이걸린다.

이진 탐색 트리할때 주로 사용하는 방법이

left(최소), right(최대), mid(중간) 값 등을 이용해서

최소와 최대를 하나씩 줄여나가면서 값을 찾는다.

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.

  //target이 없는 경우, -1을 리턴해야 합니다.
  //return arr.indexOf(target);
  //indexOf 자체가 while()문을 이용하기때문에 시간복잡도가 O(N)이걸린다.

  //이진탐색 알고리즘(O(logN))을 사용
  // 좌우 좁혀가면서 문제 풀기 다시해보자.
  
  let right = arr.length-1;
  //최댓 값 
  let left = 0;
  //최솟 값
  while(left<=right){
    let middle= parseInt((left+right)/ 2);
    //중간 값
    if(arr[middle]===target){
      return middle;
    }
     if (target < arr[middle]) {
       //이미 오름차순으로 정렬이 되어있기 때문에 가능
      right = middle - 1;
    } else if(target > arr[middle]) {
      left = middle + 1;
    }
  }
  return -1;
};