题目描述

农场里有一群牛，每头牛都有一个标签值，这些标签值组成一个升序排列的数组 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 middle
            elif labels[middle] < target:
                left = middle + 1
            else:
                right = middle - 1

完整代码 

class Solution:
    def searchInsert(self , labels: List[int], target: int) -> int:
        left,right = 0,len(labels)-1
        while left <= right:
            middle =  (left+right) // 2
            if labels[middle] == target:
                return middle
            elif labels[middle] < target:
                left = middle + 1
            else:
                right = middle - 1
        return left