1.問題描述
給定一個排序的整數(shù)組(升序)和一個要查找的目標(biāo)整數(shù)target,查找到target第1次出現(xiàn)的下標(biāo)(從0開始)泄朴,如果target不存在于數(shù)組中蔬顾,返回-1
2.問題示例
- 輸入數(shù)組[1,4,5,5,7,7,8,9,10]和目標(biāo)整數(shù)1.輸出其所在的位置為0,即第1次出現(xiàn)在第0個位置昭齐。
- 輸入數(shù)組[1,2,3,3,4,5,10]和目標(biāo)整數(shù)3尿招,輸出2,即第1次出現(xiàn)在第2個位置阱驾。
- 輸入數(shù)組[1,2,3,3,4,5,10]和目標(biāo)整數(shù)6就谜,輸出-1,即沒有出現(xiàn)過6里覆,返回-1
我的答案
class Solution():
def binarySearch(self,nums,target):
if target in nums:
output=nums.index(target)
else:
output="-1"
return output
if __name__ == "__main__":
nums=[1,4,4,5,7,7,8,9,9,10]
target=1
solution=Solution()
output=solution.binarySearch(nums,target)
print("輸入:",target)
print("位置:",output)
輸入: 1
位置: 0
參考答案
class Solution:
#參數(shù)nums:整數(shù)數(shù)組
#參數(shù)target:要查找的目標(biāo)數(shù)字
#返回值:目標(biāo)數(shù)字的第1個位置丧荐,從0開始
def binarySearch(self,nums,target):
return self.search(nums,0,len(nums)-1,target)
def search(self,nums,start,end,target):
if start>end:
return -1
mid=(start+end)//2
if nums[mid] == target:
return mid
if nums[mid]<target:
return self.search(nums,mid,end,target)
#主函數(shù)
if __name__ == "__main__":
my_solution=Solution()
nums=[1,2,3,4,5,6]
target=3
targetIndex=my_solution.binarySearch(nums,target)
print("輸入:nums=",nums," ","target=",target)
print("輸出:",targetIndex)
輸入:nums= [1, 2, 3, 4, 5, 6] target= 3
輸出: 2