[Leetcode] 704. Binary Search

#이진탐색

Problem

Leetcode algorithm study plan > 문제 링크

정렬된 배열중에서 타겟값과 일치하는 값의 위치를 찾아라. O(log n)으로

Solution

O(log n)으로 풀어야하는 문제이므로 이진탐색을 이용한다.

이진탐색 조건중인 배열의 정렬상태를 확인한다.

이진탐색은 배열의 값이 두개가 남았을때 mid는 항상 왼쪽을 바라보게된다는 조건을 이용해서 무한루프가 돌지않게 타겟을 오른쪽인덱스로 맞춰서 조건을 짜면된다.

JS Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let answer = -1
    
    let left = 0, right = nums.length -1
    while(left < right) {
        let mid = Math.floor((left+right) / 2)
        
        if (nums[mid] < target) left = mid + 1
        else right = mid
    }
    
    if (nums[right] === target) answer = right
    
    return answer
};