题解 | #牛群的位置排序# 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;
        int right = labels.length - 1;
        if (labels[left] > target) return 0;
        if (labels[right] < target) return labels.length;
        int mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (mid == left) return left + 1;
            if (labels[mid] == target) return mid;
            else if (labels[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left + 1;
    }
}

编程语言是Java。

该题考察的知识点是二分查找。

代码的文字解释如下：

1. 初始化两个指针left和right，分别指向数组的最左边界和最右边界。
2. 如果数组的最左边界的值大于目标值target，说明目标值应该插入到最左边界位置的前面，直接返回0。
3. 如果数组的最右边界的值小于目标值target，说明目标值应该插入到最右边界位置的后面，直接返回数组的长度labels.length。
4. 进入循环，当左指针小于右指针时执行以下操作：计算当前区间的中间位置mid，使用(left + right) / 2。如果中间位置mid等于左指针left，说明当前区间只有两个数字，且目标值不等于中间位置的值，那么插入位置应该在左指针位置的后面，返回left + 1。如果中间位置的值labels[mid]等于目标值target，说明找到了目标值的位置，返回mid。如果中间位置的值labels[mid]小于目标值target，说明目标值应该在中间位置的右侧，更新左指针为mid。如果中间位置的值labels[mid]大于目标值target，说明目标值应该在中间位置的左侧，更新右指针为mid。
5. 循环结束后，返回left + 1作为目标值的插入位置。