[LeetCode] Binary Search

숫자 배열 nums가 주어지고, 정수 target이 주어진다고 한다.

nums에서 target의 위치를 찾으면 인덱스를 리턴하고 만약 target이 없다면 -1을 리턴하면 되는문제이다.

Example을 보자

2번 예시처럼 nums에 target이 없다면 -1을 리턴해야한다.

const search = function(nums, target) {
    let start = 0;
    let end = nums.length -1;
    
    while(start <= end) {
        let mid = Math.floor((start + end)/2);
        if(nums[mid] === target) {
            return mid;
        }else if (nums[mid] < target) {
            start = mid + 1;
        }else if (nums[mid] > target) {
            end = mid - 1;
        }
        
    }
    
    return -1
};

먼저 초기 상태로 start 는 인덱스 0, end는 마지막 인덱스인 nums.length - 1 로 지정해주었다.

start <= end 조건을 만족하는동안 while문을 돌면서

현재 start와 end의 중앙값을 mid로 지정하고 target과 nums[mid] 값을 비교한다.

nums 는 오름차순으로 정렬되어있으므로 만약 target > nums[mid] 라면

target은 인덱스 mid+1 ~ end 사이에 존재할 수 있다.

반대로 target < nums[mid] 라면 target은 인덱스 start ~ mid-1 사이에 존재할 수 있다.

그리고 만약 target === nums[mid] 라면 그대로 mid 값을 리턴해주면 된다.

submit을 해보니

정답이었다!