Leetcode - 34. Find First and Last Position of Element in Sorted Array

문제

중복된 값이 있는 정렬된 배열이 있을때, target값이 존재하는 범위를 리턴하라. 없다면 [-1,-1]을 리턴.
단, 시간복잡도는 O(log N)을 초과할 수 없다.

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

먼저 축하할 일

Leetcode 에서 200번째로 해결한 문제이다. 딱 두달전 5/9에 100개를 돌파했는데, 속도가 붙어서 어느덧 오늘 7/9이다. 두 달동안 100문제를 풀었다. 대견한 나를 칭찬해주기!

해결 O(logN)

우선 binary search로 target값의 idx하나를 구한뒤, 그 idx로부터 좌/우로 동일한 값을 확장하며 범위를 구하는 방법. 평균적으로 O(logN) 이겠지만 최악의 경우 O(N)이 된다(모든 값이 동일한 경우).
순수하게 O(logN)으로만 해결할 수 있는 방법이 있을까?

int binary_search(int *nums, int left, int right, int target) 
{
    int mid = 0;
    while (left <= right) {
        mid = (left + right) / 2;
        if (target == nums[mid])
            return mid;
        else if (target < nums[mid])
            right = mid - 1;
        else if (nums[mid] < target)
            left = mid + 1;
    }
    return -1;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int *)malloc(sizeof(int) * 2);
    *returnSize = 2;
    int t_idx = 0;
    int l_idx = 0, r_idx = 0;
    
    t_idx = binary_search(nums, 0, numsSize -1, target);
    l_idx = t_idx;
    r_idx = t_idx;
    if (t_idx != -1) {
        while (l_idx - 1 >= 0 && nums[l_idx - 1] == nums[t_idx])
            l_idx--;
        while (r_idx + 1 <= numsSize -1 && nums[r_idx + 1] == nums[t_idx])
            r_idx++;
    }
    ret[0] = l_idx;
    ret[1] = r_idx;
    return ret;
}

two pointer 논리적 구조 구현 방안

220725에 다시 풀어본 방식. binary search로 index를 찾은뒤 중간에서 좌우로 이동하며 같은값이 있는지 찾기. 항상 배열에서 two pointer 를 찾는 것을 어려워함. 두가지 경우로 방법을 정리해보자면

1. 반복문 하나에서 처리할때, 코딩전에 먼저 생각해야할 3가지 조건
   • pointer 1이 어떤 조건에서 증/감 할지
   • pointer 2가 어떤 조건에서 증/감 해야할지
   • 반복문을 언제 탈출해야하는지
2. pointer 각각 반복문을 하나씩 처리하기 (루프 탈출 조건과 증/감 조건이 같은경우)
   이번 문제에서 풀었던 방법. 이번경우는 반복문 하나에서 처리하기에 너무 조건처리가 많아져 머리가 아팠다. 그럴땐 그냥 루프를 각각 생성하는게 편리. 앞으로 이렇게 하는게 좋겠다. 이전에 해결했던 코드보다 읽기에 더 간결함.

    while (l_idx >= 0 && nums[l_idx] == target)
        l_idx--;
    while (r_idx < numsSize && nums[r_idx] == target)
        r_idx++;

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    *returnSize = 2;
    int *ret = (int *)malloc(sizeof(int) * 2);
    
    int idx = binary_search(nums, 0, numsSize - 1, target);
    if (idx == -1) {
        ret[0] = -1;
        ret[1] = -1;
        return ret;
    }
    int l_idx = idx, r_idx = idx;
    while (l_idx >= 0 && nums[l_idx] == target)
        l_idx--;
    while (r_idx < numsSize && nums[r_idx] == target)
        r_idx++;
    
    ret[0] = l_idx + 1;
    ret[1] = r_idx - 1;
    return ret;
}