알고리즘 8 : binarySearch

문제

오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수

인자 2 : target

• number 타입의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 이진탐색 알고리즘(O(logN))을 사용해야 합니다.
• 단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
• target이 없는 경우, -1을 리턴해야 합니다.

입출력 예시

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1

 

 

코드

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.

  let first = 0
  let last = arr.length-1
  let mid = parseInt((first+last)/2)

  while(first<=last){
    
    mid = parseInt((first+last)/2)

    if(arr[mid]===target){
      return mid
    }

    else if(arr[mid]<target){//target이 오른편에 있을때
      first = mid+1
    }
    else if(arr[mid]>target){//target이 왼편에 있을때
      last = mid-1
    }

  }
  return -1
};

설명

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jkssleeky&logNo=220715543451

시간복잡도 O(logN)은 진행할수록 계산량이 줄어든다.

 

이진탐색은 배열의 중간값 arr[mid]을 찾고자 하는 target과 비교한다.

 

arr[mid]보다 작으면 arr[mid]를 기준으로 왼편의 값들로, 크다면 오른편의 값들로 계산범위를 줄인다.

 

이를 target===arr[mid]가 될 때 까지 반복한다.