本人编程小白，如果有写的不对、或者能更完善的地方请个位批评指正！
这个是leetcode的第34题，这道题的tag是数组，需要用到二分搜索法来解答
34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1]
这道题目的难点在于O(log n)，看到了O(log n)想到的基本就是二分搜索法，但怎么实现呢？大致有以下两种思路：
方法一：
思路：
先做一遍二分搜索，如果不能找到target的话返回（-1，-1）如果能找到的话然后向左、向右搜索进而找到最小和最大的target，返回index
这种解法的时间复杂度平均是O(log(n))，但当所有在数组中的数字都是一样的并且也都等于target的时候最差是O(n)
Python 代码实现：
class Solution:
def searchRange(self, A, target):
left = 0; right = len(A) - 1
while left <= right:
mid = (left + right) // 2
if A[mid] > target:
right = mid - 1
elif A[mid] < target:
left = mid + 1
else:
list = [0, 0]
if A[left] == target:
list[0] = left
if A[right] == target:
list[1] = right
for i in range(mid, right+1):
if A[i] != target:
list[1] = i - 1; break
for i in range(mid, left-1, -1):
if A[i] != target:
list[0] = i + 1; break
return list
return [-1, -1]
方法二：
思路：
做两遍二分搜索，如果不能找到target的话返回（-1，-1）如果能找到的话第一遍返回最小的index，第二遍返回最大的index，这样的话可以保证在最差的情况下时间复杂度是O(log(n))。
那么这两种二分法的搜索到底怎么实现呢？具体方法见参考文献【1】里面的2.1和2.2。
即我们希望实现找到第一个与target相等的元素和最后一个与target相等的元素：
（1）找到第一个与target相等的元素，如果没有的话返回-1：
def search_first_target(self, nums, target):
left,right = 0,len(nums)-1
while (left <= right):
mid = (left + right) >> 1
if (nums[mid] >= target): # 注意1
right = mid - 1
else:
left = mid + 1
if nums[left] == target:
return left # 注意2
else:
return -1
（2）找到最后一个与target相等的元素，如果没有的话返回-1：
def search_last_target(self, nums, target):
left,right = 0,len(nums)-1
while (left <= right):
mid = (left + right) >> 1
if (nums[mid] > target): # 注意1
right = mid - 1
else:
left = mid + 1
if nums[right] == target:
return right # 注意2
else:
return -1
最后的实现只是需要把以上两段代码合并到一起即可：
时间复杂度：log(n)
Python 代码实现：
class Solution(object):
def searchRange(self, nums, target):
l,r = 0, len(nums)-1
left,right = -1,-1
result_left, result_right = -1, -1
while(l <= r):
mid = r+(l-r)//2
if (nums[mid] > target):
r = mid - 1
elif (nums[mid] < target):
l = mid + 1
elif (nums[mid] == target):
r = mid - 1
result_left = nums[mid]
if result_left == target:
left = l
else:
return -1,-1
l,r = 0, len(nums)-1
while(l <= r):
mid = r+(l-r)//2
if (nums[mid] > target):
r = mid - 1
elif(nums[mid] < target):
l = mid + 1
elif(nums[mid] == target):
l = mid + 1
result_right = nums[mid]
if result_right == target:
right = r
return left, right
参考文献：
1.分析了二分法的不同情况，写的不错：https://www.cnblogs.com/luoxn28/p/5767571.html
