DAY3: Leecode-34

DAY 3(问题未解决)

leecode-34:在排序数组中查找元素的第一个和最后一个位置
tag:二分查找

给定一个按照升序排列的整数数组nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置
算时间复杂度要求O(log n)级别

如果数组中不存在目标值，返回[-1,-1]
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]

主要思路

1. “有序”“数组”结合起来，肯定要用到二分查找这一类；
2. 首先是找最左侧的下标，利用二分查找，首先找到与目标值target，然后因为是找最左侧的下标，把right = mid -1 来一直往左边逼近最左侧的值
3. 至于找最右侧的下标，就是将left = mid+1来逼近最右侧的下标
4. 如果没有找到则说明不存在返回-1

出现的问题：

1. 超出时间限制
   
   Java版本的二分法查找
   

二分查找的时间复杂度为什么是log2?
https://blog.****.net/u010452388/article/details/80875958
https://blog.****.net/u010452388/article/details/80891462
log N是如何得来的：对于N个数字的数组，查找到目标值只需要执行logN次（以2为底数）

log N是如何得来的：对于N个数字的数组，查找到目标值只需要执行logN次（以2为底数）
![从上表可以看出N/(2^{K)肯定是大于等于1，也就是N/(2}K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N

将Java 代码改成Python3 为什么依旧超出时间限制呢？？？（没搞明白）

用函数调用来做呢？