First Position of Target

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge

If the count of numbers is bigger than 2³², can your code work properly?

Solution

Time: O(nlogn), Space: O(1)
Binary Search
Note: if you find one possible pos, you cannot guarantee it is the first

(First-Position-of-Target.py) download

class Solution:
    # @param nums: The integer array
    # @param target: Target number to find
    # @return the first position of target in nums, position start from 0 
    def binarySearch(self, nums, target):
        # write your code here
        if nums==None or len(nums)==0:
            return -1
        front = 0
        end = len(nums) - 1

        result = sys.maxint
        while front <= end:
            mid = (front+end)/2
            if nums[mid] == target:
                # we cannot guarantee this "mid" is the first position
                if result > mid:
                    result = mid
                # we can check the previous pos
                end = mid-1

            elif nums[mid] > target:
                end = mid-1
            else:
                front = mid+1

        if result == sys.maxint:
            return -1
        else:
            return result