[LeetCode/Kotlin]Medium - 34. Find First and Last Position of Element in Sorted Array

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

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

나의 풀이

class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        var answer = intArrayOf(-1, -1)
        var start = 0
        var end = nums.lastIndex
        var mid: Int

        while (start <= end) {
            mid = (start+end)/2
            if (nums[mid] == target) {
                answer = intArrayOf(mid, mid)
                var index = 1
                while (true) {
                    if (mid-index >= 0 && nums[mid-index] == target) answer[0] = mid-index
                    if (mid+index < nums.size && nums[mid+index] == target) answer[1] = mid+index
                    index++

                    if ((mid-index < 0 || nums[mid-index] != target) && (mid+index >= nums.size || nums[mid+index] != target))
                        return answer
                }
            } else if (nums[mid] < target) {
                start = mid+1
            } else {
                end = mid-1
            }
        }

        return answer
    }
}

O(logN)

• 이분 탐색
• 만약 mid 인덱스 값이 target과 일치하면 앞뒤 값 비교