在之前ARTS打卡中，我每次都把算法、英文文档、技巧都写在一个文章里，这样对我的帮助是挺大的，但是可能给读者来说，一下子有这么多的输入，还是需要长时间的消化。

那我现在改变下方式，将每一个模块细分化，并且描述的更细致点，这样就能和大家更好地交流，更好地探讨具体的细节，也能让大家更好地消化所学的知识。

所以，后续的ARTS打卡，会尝试先将算法以及英文文档拆分开，11月，收获的季节，让我们继续前行，在秋天收获更多，学习更多。小编与你同行！

Algorithm LeetCode算法

在排序数组中查找元素的第一个和最后一个位置
(https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例1：

输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]

示例2：

输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]

解法一：线性扫描法

因为这是一个简单的一维数组，我们要在数组上进行查找，最笨的方法自然就是用常规的方法进行一个个遍历查找，在这里我们叫他线性扫描。

首先，我们对输入的数组nums先从头到尾进行遍历，当遇到第一个目标数字target时中止遍历，并记录下所在的位置。如果没有遇到数字，说明整个数组都不存在该目标，则直接返回一个找不到数字的结果即可，在这里就是 [-1,-1] 。

在找到第一个数字的前提下，我们从数组的尾部往前遍历，遇到第一个目标数字时，就是我们需要的第二个目标数字（因为最左边有一个已经存在了，所以必然存在一个最右边的数字不会产生找不到的情况）。

最后，我们输出结果即可。

/** *  * @Title      :   * @Description: 线性扫描 * @param nums * @param target * @return * @return     :int[] * @throws */ public static int[] searchRange1(int[] nums, int target) {     int[] range = {-1,-1};          // 从头到尾遍历，先查找左边的元素     for (int i = 0; i < nums.length; i++) {         if (nums[i] == target) {             range[0] = i;             break;         }     }              // 如果左边的元素找到最后也没找到，那么说明数组里不存在此元素，直接返回找不到的结果[-1,-1]     if (range[0] == -1) {         return range;     }              // 从尾到头遍历，继续查找右边的元素     for (int j = nums.length - 1; j >= 0 ; j--) {         if (nums[j] == target) {             range[1] = j;             break;         }     }              return range; }

解法二：二分查找

为什么会想到用二分查找呢？因为给出的题目里描述了，我们传入的数组是已经排过序的，二分法能有效提高查找效率。

同样的也是需要进行类似线性查找的方式，只不过这次我们查找的次数不会很多。首先，为了找到最左边（或者最右边）包含 target 的下标（而不是找到的话就返回 true ），所以在我们找到一个 target 后不能马上停止。我们需要继续搜索，直到 lo == hi 且它们在某个 target 值处下标相同。

另一个改变是 left 参数的引入，它是一个 boolean 类型的变量，指示我们在遇到 target == nums[mid] 时应该做什么。如果 left 为 true ，那么我们递归查询左区间，否则递归右区间。考虑如果我们在下标为