Find First and Last Position of Element in Sorted Array

Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Solution

func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
    var p1:Int = 0
    var p2:Int = 0
    var nofound = true
    for i in 0..<nums.count{
        if (nums[i] == target){
            if (nofound){
                p1 = i
                p2 = i
                nofound = false
            }
            else {
                p2 = i
            }
        }
    }
    if (nofound){
        return [-1, -1]
    }else{
        return [p1, p2]
    }
}

Performance

Explanation 

By the description we know that the solution has to be, O(log n) this hit us that we must only use one for the cycle. 

In this cycle, we only have to check if the target value is equal to the one in the current one, and store the position. 

P1 can only change one time, because it will store the first position, but the P2 one can be overwritten since we are looking for the last position where the target is. 

How to improve

We can reduce the time complexity from o(log n) to o(log n/2) by checking the first and last in the same cycle one going form 0 to nums.length, ant the other in the revers other, and break when we fund this to values. 

The solution propose above checks all of the model positions of the target, this market its slower the solution always will be o(log n), but with this modification will be less or equal in the worst scenery.

Leave a Comment

Your email address will not be published.