이진검색 구현

const rotatedArraySearch = function (rotated, target) {
  //입력: 부분적으로 오름차순 정렬된 정수의 배열/정수
  //출력: 타겟의 인덱스 리턴
  //배열을 반으로 나눔. 왼쪽파티/오른쪽파티 //[4,5,6],[0,1,2,3] /2
  //2가 rotated[0]보다 크거나 같으면 {rotated[0]부터 rotated[half]까지 둘러보기}
  //2가 rotated[rotated.length-1]보다 작거나 같으면
  //rotated[i] === target이면 i 리턴
  //발견하지 못하면 -1리턴

  if(!rotated.includes(target)) return -1;
  let half = parseInt(rotated.length / 2);
  if(target >= rotated[0]){
    for(let i = 0; i < half; i++){
      if(rotated[i] === target){ return i; }
    }
  } else if (target <= rotated[rotated.length-1]){
    for(let i = half; i < rotated.length; i++){
      if(rotated[i] === target){ return i; }
    }
  }
};

작동은 되는데 타임아웃.
재귀적으로 구역을 줄여야할거같다...

const rotatedArraySearch = function (rotated, target) {
  let low = 0;
  let high = rotated.length -1;
  //9,10,15,4,6,8
  //0~5까지 진행
  //mid = 0 + 5 / 2 = 2
  //target과 rotated[mid]가 같으면 리턴
  //아니면
  //rotated[2]보다 타겟이 작다면
  //rotated[2]보다 타겟이 크다면
  while (low <= high){
    let mid = parseInt((high + low) / 2);
    if(target === rotated[mid]){
      return mid;
    } else if (rotated[mid] > target){
      low = mid + 1;
    } else {
      high = mid - 1;
      // high = mid - 1;
    }
  }
  return -1;
};

arr가 홀수개일때 못찾는 것 같음; 머지 왜지
arr가 짝수개일때는 mid가 가장 큰 수임
arr가 홀수개일때는 mid가 가장 작은 수임...

const rotatedArraySearch = function (rotated, target) {
  let low = 0;
  let high = rotated.length -1;
  //9,10,15,4,6,8
  //0~5까지 진행
  //mid = 0 + 5 / 2 = 2
  //target과 rotated[mid]가 같으면 리턴
  //아니면
  //rotated[2]보다 타겟이 작다면
  //rotated[2]보다 타겟이 크다면
  while (low <= high){
    let mid = parseInt((high + low) / 2);
    if(target === rotated[mid]){
      return mid;
    } else if (rotated.length % 2 === 0 ){
      if (rotated[mid] > target){
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    } else {
      if (rotated[mid] > target){
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }    
  }
  return -1;
};

효율적인 알고리즘 어쩌고 빼고는 다 통과했다...ㅠㅠ 힝
arr의 길이가 짝수일때와 홀수일때를 분기해줌,