704. Binary Search (Easy) [TypeScript]

 

💡생각 방식

루프 돌려서 하나씩 확인해 봐서 맞다면 그 인덱스 리턴해주기

근데 문제의 제일 밑 줄을 보면 O(log n)으로 작성하라고 해줬으니 위에 생각 방식을 바꿔야 한다 (O(n) complexity를 가지고 있기 때문)

그럼 이진 탐색을 사용해서 시작과 끝 범위를 설정한 다음

중간 인덱스를 찾고 거기서 target과 비교한 다음에 오른쪽을 갈지 왼쪽을 갈지 결정해 주면 된다

그리고 거기서 타겟과 일치한다면 바로 리턴해주기!

 

💻 작성 코드

function search(nums: number[], target: number): number {
    let left: number = 0;
    let right: number = nums.length - 1;

    while (left <= right) {
        const mid: number = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

 

만약에 배열이 정렬이 되지 않았다고 가정하고, 정렬을 하면 안 되는 상황이라면?

그냥 원래 생각 방식처럼 풀어주면 된다

코드는 이렇게 짜면 된다

function search(nums: number[], target: number): number {
    for (let i: number = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }

    return -1;
}