704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Plain Text
복사

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Plain Text
복사

Constraints:

•

1 <= nums.length <= 104

•

104 < nums[i], target < 104

•

All the integers in nums are unique.

•

nums is sorted in ascending order.

My solution

정수 배열 nums 가 주어진다. 오름차순으로 정렬되어 있다. target 이 주어지면 찾는 함수를 작성하라.

있으면 인덱스를 반환하고, 없으면 -1을 반환해라.

O(log n)의 시간복잡도를 가진 알고리즘으로 작성하라.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
JavaScript
복사

find 메서드를 구현하는 것으로 생각할 수 있다. 이진 탐색을 사용한다.

시작포인터와 끝 포인터, 그리고 중앙을 가리키는 포인터가 있다.

중앙 값은 매번 루프마다 업데이트된다. 시작과 끝 포인터가 같아질 때까지는 범위가 존재하므로 계속해서 target을 찾아나갈 것이다.

mid 인덱스에 접근했을 때의 값이 내가 찾으려는 target인지 조건문으로 검사한다. 

맞으면 true를 반환하면 된다.

이 때 만약 target 보다 크다면 그 값을 기준으로 끝 포인터를 업데이트해주어도 그보다 더 큰 값을 검사할 필요가 없기 때문에 탐색이 확 줄어든다. 

반대로 target보다 작다면 시작 포인터를 그 값보다 1 크도록 업데이트해서 탐색 범위를 확 좁혀줄 수 있다.

따라서 반복문을 사용한 이진 탐색은 아래와 같이 구현할 수 있다.(https://blockdmask.tistory.com/167)

function BinarySearch(arr, len, key) {
    let start = 0;
    let end = len - 1;
    let mid;

    while (end - start >= 0) {
      mid = (start + end) / 2; // 중앙 값

      if (arr[mid] == key) {
        // key값을 찾았을때
        return true;
      }
      if (arr[mid] > key) {
        // key값이 mid의 값보다 작을때 (왼쪽으로)
        end = mid - 1;
      } else {
        // key값이 mid의 값보다 클때 (오른쪽으로)
        start = mid + 1;
      }
    }
    return false;
  }
JavaScript
복사

여기서는 mid가 key가 되자마자 이 인덱스를 반환해주거나, 아예 찾지 못하면 false 대신 -1을 반환해주어야 하므로 함수의 return statement를 변경하면 된다.

function BinarySearch(arr, len, key) {
  let start = 0;
  let end = len - 1;
  let mid;

  while (end - start >= 0) {
    mid = Math.floor((start + end) / 2);
    if (arr[mid] === key) return mid;
    if (arr[mid] > key) end = mid - 1;
    else start = mid + 1;
  }
  return -1;
}
JavaScript
복사

이진탐색은 재귀로도 구현할 수 있다. 로직은 거의 같다.

함수를 실행하면서 start 포인터가 end 포인터보다 커지는 시점에 return false를 해주는 방식이고, start, end 포인터를 인수를 통해 전달하면서 줄여나가고 타겟을 찾는다.

function RecursiveBinarySearch(arr, start, end, key) {
    if (start > end) return -1; // key 값이 없을 때

    const mid = Math.floor((start + end) / 2);
    if (arr[mid] === key) return mid;
    if (arr[mid] > key) return RecursiveBinarySearch(arr, start, mid - 1, key);
    return RecursiveBinarySearch(arr, mid + 1, end, key);
  }

  return RecursiveBinarySearch(nums, 0, nums.length - 1, target);
JavaScript
복사

코드라인이 줄어든 대신 파라미터가 1개 늘어났고 런타임은 거의 똑같았다.(68, 67ms)

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = function (nums, target) {
  function BinarySearch(arr, len, key) {
    let start = 0;
    let end = len - 1;
    let mid;

    while (end - start >= 0) {
      mid = Math.floor((start + end) / 2);
      if (arr[mid] === key) return mid;
      if (arr[mid] > key) end = mid - 1;
      else start = mid + 1;
    }
    return -1;
  }

  return BinarySearch(nums, nums.length, target);
};

describe('BinarySearch', () => {
  it('TC1', () => {
    expect(search([-1, 0, 3, 5, 9, 12], 9)).toStrictEqual(4);
  });
  it('TC2', () => {
    expect(search([-1, 0, 3, 5, 9, 12], 2)).toStrictEqual(-1);
  });
});
JavaScript
복사