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编程语言。

这个题目考察的是二分查找算法。给定一个已排序的整数数组 labels 和一个目标值 target，要求找出将 target 插入到数组中的正确位置，并返回插入位置的索引。如果 target 已经存在于数组中，则直接返回其索引；如果 target 在数组中不存在，则返回它应该插入的位置的索引。

代码的逻辑解释如下：

1. 们定义左指针 left 初始化为数组的第一个元素的索引，右指针 right 初始化为数组最后一个元素的索引。
2. 如果目标值比数组的第一个元素还要小，说明插入位置在数组的最前面，直接返回 0。
3. 如果目标值比数组的最后一个元素还要大，说明插入位置在数组的最后面，直接返回数组长度。
4. 使用二分查找的思想，在循环中查找插入位置。
5. 当左指针小于右指针时，执行循环。
6. 计算中间位置 mid，并比较中间位置的元素与目标值的大小。
7. 如果中间位置的元素等于目标值，说明目标值已经存在于数组中，直接返回中间位置的索引。
8. 如果中间位置的元素小于目标值，说明目标值应该插入到中间位置的右侧，更新左指针 
9. 如果中间位置的元素大于目标值，说明目标值应该插入到中间位置的左侧，更新右指针 
10. 当循环结束时，左指针和右指针相邻，说明已找到插入位置，返回左指针
11. 如果循环结束时左指针和右指针不相邻，说明目标值在数组中不存在，返回左指针