描述

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

样例

在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2.

挑战

如果数组中的整数个数超过了2^32,你的算法是否会出错?

如果对二分查找比较陌生话,那么讲个小游戏,猜数字,在0-10000中随机取个数,让你猜,猜错了告诉你大了还是小了.

那么第一想法是什么?报中位数?对,不停的报中位数直到剩下最后一个数,这个数就是所需数,这个方法是比一个一个遍历要快非常多所需步骤也仅为log2n 回到正题

class Solution: def binarySearch(self, nums, target): # write your code here start=0 end=len(nums) mid=int(end/2) while start<=end: n_mid = nums[mid] if n_mid <target: #right start=mid+1 mid=int((end+start)/2) elif n_mid >target: #left end=mid-1 mid=int((end-start)/2) else: while nums[mid]==target: mid-=1 return mid+1 return -1

参考于这篇做了一些修正,在没有重复的情况下,else的部分去除.直接return mid+1