[알고리즘] #Binary Search

출처 : https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

 

문제 해석

704. 이진탐색

오름차순으로 정렬된 정수형 배열 nums와 정수형 변수 target이 주어졌을 때, nums 배열에서 target 값을 찾는 function을 써라.

만약 배열에 target 값이 존재한다면 인덱스 값을 리턴하고, 없으면 -1을 리턴한다.

 

제약사항

nums 안에 모든 정수들은 중복된 값이 없다.

nums는 오름차순으로 정렬되어있다.

 

 

풀이

이 문제에서 포인트가 되는 부분은 오름차순 정렬, 중복된 값이 없음이다.

오름차순으로 정렬되어있으니 배열의 중간값과 target을 비교해서 배열을 잘라가며 배열의 길이가 1개가 될 때까지 반복한다.

그런데 여기서 주의해야할 점은 index 값을 리턴하려면 배열을 자를 때 index 값도 신경써줘야한다.

 

var search = function(nums, target) {
    let idx = 0

    while(1) {
        let mid = parseInt(nums.length/2)
        if (mid === 0) {
            return nums[mid] === target ? 0 : -1
        } else if (nums[mid] === target) {
            return idx + mid
        } else if(nums[mid] > target) {
            nums = nums.slice(0, mid)
        } else {
            idx += mid
            nums = nums.slice(mid, nums.length)
        }
    }
}