原題
給定一個(gè)排序的整數(shù)數(shù)組（升序）和一個(gè)要查找的整數(shù)target，用O(logn)的時(shí)間查找到target第一次出現(xiàn)的下標(biāo)（從0開始）青抛，如果target不存在于數(shù)組中灸叼，返回-1汉额。
在數(shù)組 [1, 2, 3, 3, 4, 5, 10] 中二分查找3印叁，返回2洼专。
解題思路
- 首先使用start + 1 < end =>表示相交或者相鄰?fù)Ｖ?/li>
- 因?yàn)槭钦业谝淮纬霈F(xiàn)的位置所以
if nums[mid] < target:
start = mid
else:
end = mid
- 最后start和end可能相等可能不等鼻百，統(tǒng)一模板砌创，兩個(gè)都check件余，順序依照題目而定良姆，本題先chcek start
完整代碼
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):
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] < target:
start = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
