14.二分查找

描述

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

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):
            low = 0
            high = len(nums) - 1
            while low <= high:
                mid = low + (high - low) // 2
                if  nums[mid] == target:
                    while(mid >= 0):#新增加的while和if用于解决有重复数字的情况，并保证每次都输出第一次出现的target的下标
                        if nums[mid] != target:
                            break

                        mid = mid - 1
                    if mid <= -1:
                        return 0
                    return mid + 1#多减了一次，所以输出时+1
                elif  target > nums[mid]:
                    low = mid + 1
                else:
                    high = mid - 1

            return -1



nums = [4,5,9,12,13,14,15,15,18]
so = Solution()
print(so.binarySearch(nums,9))