题解 | #牛群的位置排序#

知识点：二分查找

题目要求使用时间复杂度为 O(log n) 的算法。我们就需要使用二分法来查找对应数据，这道题的难点在于对于数组中不存在的元素target，我们如何找到该target应该插入的位置。如果不存在，应该找到它按顺序插入的位置，我们先假设left和right已经相等，此时，我们还并没有找到target，故我们应该在当前位置的下一个位置作为target的插入位置，即mid + 1，也就是最终left所处的位置。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param labels int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int searchInsert (int[] labels, int target) {
        // write code here
        int left = 0, right = labels.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(labels[mid] == target) {
                return mid;
            }else if(labels[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }
}