[LeetCode] Binary Search

문제 링크

https://leetcode.com/problems/binary-search/description/

문제 설명

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

Example 2:

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

 

array를 받았을 때, BS를 통해 해당하는 target을 찾는 방법입니다.

해당 array는 이미 정렬이 되어있는 상태이므로, 간단하게 구현할 수 있습니다.

내 풀이

function search(nums: number[], target: number): number {
	// 재귀함수를 통한 반복 진행
    function BS(start: number, end: number): number {
    	// start보다 end값이 커진다면
        // 찾는 값이 없다는 것이므로 -1 반환
        if (start > end) {
            return -1;
        }
		
        // 중간 인덱스 확인하기
        // Math.round를 통해 반올림을 진행합니다.
        // 2.5 -> 3
        let mid = Math.round((start + end) / 2);
        if (nums[mid] < target) {
            return BS(mid + 1, end);
        } else if (nums[mid] > target) {
            return BS(start, mid - 1);
        } else {
            return mid;
        }
    }
    return BS(0, nums.length - 1)
};

 

다른 사람의 풀이

해당 풀이는 스파르타코딩클럽_알고리즘을 참조하였습니다.

오늘 배운 점

이진 탐색 트리가 어떻게 설계되었는지 확인할 수 있었습니다.

중간을 먼저 확인하고, Target보다 작으면 오른쪽으로, Target보다 크면 오른쪽으로 갑니다.