Algorithm problem-10

1. 문제

• binary search 문제
• 배열에서 타겟의 값을 찾아 인덱스를 리턴, 없으면 -1 리턴

2. 시도

• arr의 인덱스를 추출해야 하니까 arr은 immutable해야함
• 시작점과 끝점을 인덱스로 지정하고
• arr의 중간점을 찾아 중간점과 타겟을 비교
• 중간점의 값보다 타겟이 큰지 작은지를 비교해
• 시작점 또는 끝점을 변경해서 서치
• 중간점을 계속 바꿔주려면 중간점의 기준도 변경되는 시작점과 끝점으로 해야함
• 탐색의 기준점은 중간점의 인덱스로 시작하고
• 이걸 또 재귀하면 반의 반의....반을 계속 실행
• 찾다가 없으면 탈출해서 리턴 -1

3. 수도코드

• 힌트를 참고하긴 했지만, 잘 풀어내긴 했다

const binarySearch = function (arr, target) {
  let start = 0; // 처음의 시작은 0번부터
  let end = arr.length - 1; // 처음의 끝은 마지막 인덱스
  // 시작점과 끝점이 같아지면 더 이상 검색할 값이 없다는 의미
  while (start <= end) { 
    // 중간점은 변경되는 시작점 과 끝점을 기준으로 잡아야 함께 변경됨
    let mid = parseInt((start + end) / 2); 
    if (target > arr[mid]) {
      start = mid + 1; // 중간보다 크면 중간+1을 시작점으로 변경
    }
    else if (target < arr[mid]) {
      end = mid - 1; // 중간보다 작으면 중간-1을 끝점으로 변경
    }
    else {return mid;} // 둘 다 아니면 같은거니까 중간점 리턴
  }
  return -1; // 시작점과 끝점이 같아질 때까지 돌아도 안나오면 값이 없는 경우
};

4. 레퍼런스

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