알고리즘 문제풀이를 진행하다 너무 헷갈리는 개념이 나와서 정리!
문제만 보고도 어떤 알고리즘이 필요한 지 아는 능력이 있었으면..🥲

📍 이분 탐색

이분 탐색이란 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색합니다.
(출처 - 나무위키)

그래서 방법은?

오름차순으로 정리된 배열이 있습니다.

arr = [ 2, 8, 14, 38, 56, 88, 90 ]

여기서 38 에 해당하는 위치(index)를 찾으려고 한다면,

1️⃣ arr 배열에서의 중간 값을 구합니다.

const solution = (target, arr) => {
  let start = 0;
  let end = length-1;

  const mid = parseInt((start+end)/2); //47

...중략

2️⃣ 중간 값과 검색 값을 비교합니다.
3️⃣ 중간 값이 검색 값과 같다면 종료합니다. (mid = key)

const solution = (target, arr) => {
  let start = 0;
  let end = length-1;

  //start와 end의 간격이 좁혀지다가 start가 end보다 커지게 되면 반복을 종료
  while(start <= end){ 

  const mid = parseInt((start + end) / 2);

  if(target === arr[mid]){
    return mid;
  }
  
...중략

4️⃣ 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < target)
5️⃣ 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > target)

const solution = (target, arr) => {
  let start = 0;
  let end = length-1;

  while(start <= end){ 

  const mid = parseInt((start + end) / 2);

  if(target === arr[mid]){
    return mid;
  }else if(target < arr[mid]) {
    return end = mid-1;
  }else{
    return start = mid-1;
  }
   return -1 ; 
  }
}