[자료구조/알고리즘] 211024 BinarySearch #while문 #parseInt #Math.floor()

📌 BinarySearch

이진탐색 문제이다. 배열(=arr)과 정수(=target)가 주어지고 그 배열에서 그 정수를 탐색한다. target과 배열의 인덱스값이 일치하면 그 인덱스를 리턴해야 한다. 아예 문제에서 이진탐색으로 풀라고 하고 있고, 단순히 배열 순회로는 풀수 없다고 명시하고 있다. 아래 입출력 예시를 보면 더 이해하기 쉽다.

주의사항

• 이진탐색 알고리즘(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

처음 생각했을 때 배열을 두개로 쪼개어 접근해야 한하는 건 알겠는데 그걸 어떻게 코드로 작성해야 할지 너무 막막했다.. 단순배열 순회만 생각했었으니까 말이다.
그래서 일단 이 문제는 구글링으로 문제를 해결하고 코드를 이해하기로 했다. 다른 건 구글링 해서 찾은것도 이해못한 경우가 허다해서 그나마 다행이라는 생각..

수도코드

1) 세개의 변수 설정

• 첫번째 인덱스 / 마지막 인덱스/ 중간인덱스

2) 마지막 인덱스가 첫번째 인덱스보다 클 때(찾을때까지 계속 반복해야 하므로 while)
3) 그렇지 않은 경우 -1 리턴

이것만 보고 틀을 짜 보자면

const binarySearch = function (arr, target) {
let first = 0;
let last = arr.length -1 ;
let mid;
//
while(first <= last) {
//
}
return -1 
}

대충 이렇다. 이제 while문안에서는 target과 arr의 인덱스의 값이 일치할 때는 return 인덱스 를 해야 하고, 그렇지 않을 때도 두개의 경우로 나눠야 했다. arr의 중간 인덱스의 값이 target보다 클 때 or 크지않을 때로.
이제 선언만 해준 중간인덱스 값을 활용해야 한다. 그다음 수도코드를 작성한다.

const binarySearch = function (arr, target) {
let first = 0;//첫번째 인덱스 초기화
let last = arr.length -1 ;//마지막 인덱스
let mid;//중간인덱스
//
while(first <= last) {
//mid 는 탐색대상의 중간 인덱스 값을 뽑아낸다(Math.floor()이용)
  //만약 arr[mid] 과 target이 일치한다면 return mid
  // 그렇지 않다면
    //arr[mid]가 target보다 클 때 마지막 인덱스에 중간인덱스-1을 재할당(반복)
    //arr[mid]가 target보다 작을 때 첫번째 인덱스에 중간인덱스+1을 재할당(반복)
}
return -1 
}

이렇게 수도코드를 작성한다. mid는 Math.floor(first + last / 2) 또는 parseInt((first + last) /2) 를 해도 상관은 없다. 정수를 뽑아내려고 하는 것이기에.

//만약 arr[mid] 과 target이 일치한다면 return mid
if(target === arr[mid]) { return mid }
else { // 그렇지 않다면
 // target < arr[mid] 라면 last = mid - 1
 // target > arr[mid] 라면 first = mid + 1
}

last = mid -1// why?
중간인덱스 값을 구해놓고 arr[mid]가 target보다 클 때는 중간인덱스에서 -1을 해주면서 일치할 때까지 계속 반복해줘야 한다는 것이다.

first = mid +1// why?
중간인덱스 값을 구해놓고 arr[mid]가 target보다 작을 때는 중간인덱스에서 +1을 해주면서 일치할 때까지 계속 반복해줘야 한다는 것이다.