本文主要是介绍面试高频 牛群的位置排序---搜索插入位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
农场里有一群牛，每头牛都有一个标签值，这些标签值组成一个升序排列的数组 labels。现在农场主想知道，给定一个目标标签值 target，如果在牛群中存在这个标签，返回它的位置，如果不存在，返回它按顺序插入的位置。请你编写一个程序，实现这个功能。
此题等同于代码随想录搜索插入位置那道题
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
- 输入: [1,3,5,6], 5
- 输出: 2
示例 2:
- 输入: [1,3,5,6], 2
- 输出: 1
示例 3:
- 输入: [1,3,5,6], 7
- 输出: 4
示例 4:
- 输入: [1,3,5,6], 0
- 输出: 0
题目解析
首先我们可以看到labels是一个升序排列的数组，即从小到大排列的有序数组，可知可以用二分查找来解决。而且根据题目要求，不难得出，这道题有4种情况，如下图所示：
算法原理
二分法的思路如下图：
用二分查找来解决这4种情况，设立左边界left和右边界right，左边界为0，右边界为len(labels)-1，然后设置中值middle = （left + right）// 2，“//”用来整除向下取整，如3//2为1。
第2种情况又分为3种情况：
1、当 labels[middle]小于目标值target的时候，说明目标值在右边，右边界right不变，因为 labels[middle] != target，所以左边界left变为middle+1
2、当 labels[middle]大于目标值target的时候，说明目标值在左边，左边界left不变，因为 labels[middle] != target，所以右边界left变为middle-1
3、当 labels[middle]等于目标值target的时候，直接返回middle就是target的下标
部分代码
if labels[middle] == target:return middleelif labels[middle] < target:left = middle + 1else:right = middle - 1完整代码
class Solution:def searchInsert(self , labels: List[int], target: int) -> int:left,right = 0,len(labels)-1while left <= right:middle = (left+right) // 2if labels[middle] == target:return middleelif labels[middle] < target:left = middle + 1else:right = middle - 1return left这篇关于面试高频 牛群的位置排序---搜索插入位置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
