day3

03.First Position of Target
Description
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
Example 1:
    Input:  [1,4,4,5,7,7,8,9,9,10]，1
    Output: 0
    
    Explanation: 
    the first index of  1 is 0.

Example 2:
    Input: [1, 2, 3, 3, 4, 5, 10]，3
    Output: 2
    
    Explanation: 
    the first index of 3 is 2.

Example 3:
    Input: [1, 2, 3, 3, 4, 5, 10]，6
    Output: -1
    
    Explanation: 
    Not exist 6 in array.

oj:https://www.lintcode.com/problem/first-position-of-target/description
注意：这道题也可以变为找到最后一个位置，大家都可以试试。


-------------------------------------------------------------------------------------
class Solution:
"""
@param nums: The integer array.
@param target: Target to find.
@return: The first position of target. Position starts from 0.
"""
def binarySearch(self, nums, target):
    left = 0
    right = len(nums)-1
    res = 0
    while left<=right:
        mid = left+(right-left)//2
        if target>nums[mid]:
            left = mid+1
        else:
            right = mid-1
            res = mid
    if nums[res] == target:
        return res
    return -1