[Algorithm]

🦕 binarySearch

🍀 문제 풀이

const binarySearch = function (arr, target) {
  let start = 0;
  let end = arr.length - 1
  let mid
  
  while(start <= end){ //점점 좁혀지다가 start와 end의 순서가 어긋나게 되면 반복을 종료한다
  
  mid = parseInt((start + end)/2)
  
  if(target === arr[mid]){
    return mid;
  } else{
    if(target<arr[mid]){
      end = mid - 1
    }
    else{
      start = mid + 1
    }
  }
  }
  return -1

};

🌲 회고

이진 탐색이란 데이터가 정렬되었는 배열에서 특정한 값을 찾아내는 알고리즘!!
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비표한다. x가 중간 값보다 작으면 중간 값을 기준으로 왼쪽 데이터들을 대상으로, x가 중간값보다 크면 배열의 오른쪽을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의의로 선택하여 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
이진탐색(O(logN))은 단순한 배열 순회 (O(N))보다 시간복잡도에서 크게 이점을 같는다.
처음에 접할때만해도 이거 무슨 말이지? 했지만 한번 두번 세번 푸니 아 맞다 이렇게 했지 ㅋㅋ 감이 온다...물론 아쉬운건 재귀적으로 풀지 못한 나에게 한심...재귀함수 기억이 가물가물하다는 점...