LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置（Java实现及解析）

题目：

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1: 输入: dividend = 10, divisor = 3 输出: 3 示例 2: 输入: dividend = 7, divisor = -3 输出: -2

说明: 被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2 ³¹, 2³¹ − 1]。本题中，如果除法结果溢出，则返回 2³¹ − 1。

解析：

  由于数组是顺序的，故推荐使用二分搜索，这是非常快速的，然则二分搜索具有不稳定性，即使得到了目标值，也不一定是它第一次或者最后一次出现的位置，此时只需直接向前和向后搜索，得到目标值的最小和最大索引。

代码：

public class LeetCode34_2 { public static int[] searchRange(int[] nums, int target) { int indexLen = nums.length - 1; // 空数组 if (indexLen == -1) { return new int[] { -1, -1 }; } // 小于最小的，大于最大的 if (nums[0] > target || nums[indexLen] < target) { return new int[] { -1, -1 }; } // 二分查找 int index = binarySearch(nums, target); // 不存在 if (index == -1) { return new int[] { -1, -1 }; } // 最大，最小值 int small = index; int big = index; // 匹配到的且下标最小的值 while (true) { if (small == 0) { break; } if (nums[--small] != target) { ++small; break; } } // 匹配到的且下标最大的值 while (true) { if (big == indexLen) { break; } if (nums[++big] != target) { --big; break; } } // 返回结果 return new int[] { small, big }; } public static int binarySearch(int[] nums, int target) { int low = 0; int high = nums.length - 1; // 二分查找 while (low <= high) { int mid = (low + high) >> 1; if (target < nums[mid]) { high = mid - 1; } else if (target > nums[mid]) { low = mid + 1; } else { return mid; } } // 没有找到返回-1 return -1; } public static void main(String[] args) { int[] nums = new int[] { 2, 2, 2, 2, 5, 5, 5, 5, 9, 10, 25, 36, 39, 45 }; // int[] nums = new int[] { 1, 2, 3, 5, 9, 10, 25, 36, 39, 45 }; int binarySort = binarySearch(nums, 5); System.out.println(binarySort); int[] searchRange = searchRange(nums, 9); System.out.println(Arrays.toString(searchRange)); } }

运行：