704. Binary Search 풀이 - js

해당 포스팅은 릿코드 704번 Binary Search 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 이진탐색 구현 문제이다.

문제

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.

input으로 정렬된 정수 배열인 nums와 정수 target이 주어진다.
nums에서 target의 위치를 리턴해야 한다.
만약 target이 nums에 존재하지 않을 시 -1을 리턴한다.

풀이

시간복잡도 O(log n)으로 풀어야 하므로 이진탐색 문제이다.

주의해야 할 점은 nums의 원소가 하나일 때이다.

원소가 한 개일 때 start와 end가 서로 0으로 같으므로 반복문의 조건식을 (start <= end)로 설정하자. 그다음 반복문 안에 nums[mid] > target ? end = mid -1 : start = mid + 1를 걸어주자. end = mid-1에서 mid에 -1을 해주지 않는다면 무한 루프를 돈다.

전체 코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let start = 0;
    let end = nums.length -1;
    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (target === nums[mid]) return mid;
        nums[mid] > target ? end = mid -1 : start = mid + 1;
    }
    return -1;
};