이진탐색 알고리즘 (이분법?)

이진탐색

오름차순인 숫자 nums 배열과 찾아야할 target을 인자로 주면,
target이 몇 번째 index인지 return 해주세요.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
설명: 찾지 못하면 -1로 return 해주세요.
nums 배열에 있는 요소는 서로 중복된 값이 없습니다.

---> 이진탐색으로 값을 찾는 방법

처음에는 배열의 총 길이의 절반에 해당하는 값을 타겟값과 비교하여 오른쪽과 왼쪽을 자르며 배열을 줄이면서 타겟값의 인덱스를 찾는 방법으로 접근했다 하지만 그렇게되면 결국 타겟값에 가까워지긴하지만 배열이 잘려 그 타겟값의 인덱스를 구하지 못하게 된다.

고민하던 도중 어디서 많이 본 방법이지 생각하다 대학교때 배운 수치해석의 이분법이 생각났다. 이분법도 근이 있다고 판단되는 범위(f(x1)*f(X2)<0)를 임의로 정하고 중간값을 찾아 타겟값을 비교한다음 처음과 끝값 중 하나를 중간값으로 바꿔주는 방법이다. 매트랩으로 구현해본 적이 있어 이것도 그 방법으로 할 수 있나 ? 재귀함수로로 가능한가 ? 생각하다 내가 이분법은 연속일때만 가능한데 배열은 연속이 아니라 적용시킬 수 없다.

오 그래도 중간값을 이용하면 인덱스를 찾을수 있겠네 !! 생각해놓고 이분법에 빠져 재귀함수를 열심히 생각하다 결국 재현님과 함께 중간값을 이용해 구현했다.

const findIndex = (nums, target) => {
  let left = 0
  let right = nums.length -1
  while(left < right){
    let middle = Math.round((left+right)/2)
    if( nums[middle] === target) {
      return middle
    }
    else if(nums[middle] < target) {
      left = middle + 1
    } else if(nums[middle] > target){
      right = middle - 1
    }
  } 
  if(left === right) {
    return right // return left
  }
  return -1
}

처음인덱스와 끝인덱스를 찾아 중간 인덱스를 구해 각 left와 right에 넣어준다.
두개의 (left,right)처음과 끝값을 이용해 중간 인덱스를 구해 middle에 넣어준다.
중간 인덱스로 중간값을 구했으면 타켓값과 비교한다.
만약 타켓의 값이 중간값과 같으면 바로 리턴한다.
타켓의 값이 중간값보다 크다면 타겟값이 중간값보다 오른쪽에 있는 거니까 중간값을 left값으로 바꿔준다. 이때 중간값이 타겟값이 아니라는 것은 증명이 됐으니 left값을 중간값의 +1한 값으로 설정해 주면 더 빠르게 찾을 수 있다.(left = middle + 1)


반대로 타겟의 값이 중간값보다 작다면 같은 원리로 중간값보다 오른쪽에 있다는 것이니 right에 중간값을 넣어주는데 중간값은 타겟값이 아니라는 것이 증명됐으니 중간값의 -1한 값을 대입해준다(right = middle - 1)


이 과정을 반복하다 보면 타겟값에 가까워지고 반복이 끝날때까지 중간값이 타겟값을 찾지못하고 left와 right가 만나게 되어 중간값이 없어지면 그 인덱스가 타겟값이 되게된다.


수학이랑 연결되니 재밌군 !!!!!😋