题解 | #牛群的位置排序#
牛群的位置排序
https://www.nowcoder.com/practice/87c81fa27b9a45c49ed56650dfa6f51b
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 start = 0; int end = labels.length - 1; if (target > labels[labels.length - 1]) { return labels.length; } if (target < labels[0]) { return 0; } while (start <= end) { int mid = (start + end) / 2; if (labels[mid] < target) { start = mid + 1; } else if (labels[mid] > target) { end = mid - 1; }else{ return mid; } } return start; } }
本题考察的知识点为数组排序,所用语言为java
首先需要分析两个极端情况
1.目标值比数组中的所有值都小,此时插入位置为0
2.目标值比数组中的所有值都大,此时插入位置为数组长度
如果不是这两个极端情况之一,进行二分查找
目标值比中间值大的话,start大小变为mid+1
目标值比中间值小的话,end大小变为mid-1
如果二分查找没找到目标值,插入位置为下标start