本人编程小白，如果有写的不对、或者能更完善的地方请个位批评指正！
这个是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)
第二种： 做两遍二分搜索，如果不能找到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 while(l <= r): mid = (l+r)//2 if (nums[mid] >= target): r = mid - 1 else: l = mid + 1 if nums[l] == target: print (nums[left],target) left = l else: return -1, -1 l,r = 0, len(nums)-1 while(l <= r): mid = (l+r)//2 if (nums[mid] > target): r = mid - 1 else: l = mid + 1 if nums[r] == target: right = r return left, right if __name__ == "__main__": nums = [5,7,7,8,8,10] target = 3 print(searchRange(0,nums,target))
参考文献：
1.分析了二分法的不同情况，写的不错：https://www.cnblogs.com/luoxn28/p/5767571.html
Leetcode 34 Find First and Last Position of Element in Sorted Array 解题思路 (python)
原文：https://www.cnblogs.com/samstudy/p/10167958.html