# 34. Find First and Last Position of Element in Sorted Array
LeetCode Link (opens new window)
Given an array of integers nums sorted in ascending order, and a target value target. Find the starting and ending position of a given target value in the array.
If the target value does not exist in the array, return [-1, -1].
Advanced: Can you write an algorithm with O(log n) runtime complexity?
Example 1:
- Input: nums = [5,7,7,8,8,10], target = 8
- Output: [3,4]
Example 2:
- Input: nums = [5,7,7,8,8,10], target = 6
- Output: [-1,-1]
Example 3:
- Input: nums = [], target = 0
- Output: [-1,-1]
# Approach
If you're not very familiar with the basics, it's not recommended to look at concise code immediately, as it might hide too much logic, leading to a lack of understanding of specific details even if the code gets accepted!
If you are not familiar with binary search, work on these two problems first:
Below, I will discuss all possible scenarios.
Finding the left and right boundaries of the target in the array involves the following three scenarios:
- Scenario 1: The target is out of the array bounds, either on the right or left. For example, for the array {3, 4, 5}, if the target is 2 or if the array is {3, 4, 5}, and the target is 6, then it should return {-1, -1}.
- Scenario 2: The target is within the array bounds, but the array does not contain the target. For example, for the array {3, 6, 7}, if the target is 5, then it should return {-1, -1}.
- Scenario 3: The target is within the array bounds and the array contains the target. For example, for the array {3, 6, 7}, if the target is 6, then it should return {1, 1}.
Considering these three scenarios indicates a clear understanding.
Next, let's find the left and right boundaries.
We will use binary search to find the left and right boundaries. For code clarity, I will write two separate binary search functions to find the left and right boundaries.
For those just starting with binary search, it is not advisable to attempt finding both boundaries with a single binary search. It's easy to get confused and lost. It's better to write two separate binary searches to find the left and right boundaries reliably.
# Finding the Right Boundary
Let's first find the right boundary. As explained in 0704.Binary Search (opens new window), you need to clarify the loop invariant to know when to use while (left <= right) and when to use while (left < right) in binary search.
Here, I'll use the while (left <= right) method with a [left, right] interval, meaning a closed interval on both ends.
Let's write the code:
// Binary search to find the right boundary (not including the target)
// If rightBorder is not set (i.e., target is on the left side of the array, e.g., array [3,3], target is 2), this handles scenario one
int getRightBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // Define search interval as [left, right]
int rightBorder = -2; // Record the case where rightBorder is not set
while (left <= right) { // [left, right] interval is valid when left equals right
int middle = left + ((right - left) / 2); // Prevent overflow; equivalent to (left + right)/2
if (nums[middle] > target) {
right = middle - 1; // Target is in the left interval, so [left, middle - 1]
} else { // When nums[middle] == target, update left to find the right border
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Finding the Left Boundary
// Binary search to find the left boundary (not including the target)
// If leftBorder is not set (i.e., target is on the right side of the array, e.g., array [3,3], target is 4), this handles scenario one
int getLeftBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // Define search interval as [left, right]
int leftBorder = -2; // Record the case where leftBorder is not set
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) { // Search for the left boundary; update right when nums[middle] == target
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Handling the Three Scenarios
Once you've calculated the left and right boundaries, look at the main code, which covers the three scenarios:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
// Scenario 1
if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
// Scenario 3
if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
// Scenario 2
return {-1, -1};
}
private:
int getRightBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int rightBorder = -2; // Record the case where rightBorder is not set
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else { // Search for the right boundary; update left when nums[middle] == target
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
int getLeftBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int leftBorder = -2; // Record the case where leftBorder is not set
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) { // Search for the left boundary; update right when nums[middle] == target
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
This code can be further optimized for brevity, for instance, by merging the functions for finding the left and right boundaries.
However, splitting them as shown makes it clearer, and it fully presents the handling logic for the three scenarios.
# Summary
For beginners, it is recommended to break this problem down step by step. Once you've understood the three scenarios, focus on finding the right boundary, then the left boundary, and finally making the judgment based on both boundaries.
Avoid trying to find both boundaries with a single pass, as this can lead to confusion and missteps.
# Other Language Versions
# Java
class Solution {
int[] searchRange(int[] nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
// Scenario 1
if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
// Scenario 3
if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
// Scenario 2
return new int[]{-1, -1};
}
int getRightBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int rightBorder = -2; // Record the case where rightBorder is not set
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else { // Search for the right boundary; update left when nums[middle] == target
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
int getLeftBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int leftBorder = -2; // Record the case where leftBorder is not set
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) { // Search for the left boundary; update right when nums[middle] == target
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Solution 2
// 1. First, perform a binary search for the target in the nums array.
// 2. If the binary search fails, binarySearch will return -1, indicating that the target is not in nums. In this case, searchRange should return {-1, -1} directly.
// 3. If the binary search succeeds, binarySearch returns the index of one occurrence of the target in nums. Then, find the range by shifting pointers left and right.
class Solution {
public int[] searchRange(int[] nums, int target) {
int index = binarySearch(nums, target); // Binary search
if (index == -1) { // The target does not exist in nums, return {-1, -1}
return new int[] {-1, -1}; // Anonymous array
}
// The target exists in nums, use pointers to find the applicable range
int left = index;
int right = index;
// Move left to find the left boundary
while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // Prevent out of bounds. Logical short-circuit, order not changeable
left--;
}
// Move right to find the right boundary
while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // Prevent out of bounds.
right++;
}
return new int[] {left, right};
}
/**
* Binary search
* @param nums
* @param target
*/
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // Constant: closed interval on both ends
while (left <= right) { // Constant: closed interval on both ends
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1; // Constant: closed interval on both ends
}
}
return -1; // Not found
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Solution 3
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = searchLeft(nums, target);
int right = searchRight(nums, target);
return new int[]{left, right};
}
public int searchLeft(int[] nums, int target){
// Find the first occurrence of the element
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Reduce >= because we're finding the first instance
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// right = left - 1
// Use right if there's an answer
if (right >= 0 && right < nums.length && nums[right] == target) {
return right;
}
if (left >= 0 && left < nums.length && nums[left] == target) {
return left;
}
return -1;
}
public int searchRight(int[] nums, int target){
// Find the last occurrence
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Increase <= because we're finding the last instance
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// left = right + 1
// Find last occurrence, use left if there’s an answer
if (left >= 0 && left < nums.length && nums[left] == target) {
return left;
}
if (right >= 0 && right < nums.length && nums[right] == target) {
return right;
}
return -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# C#
public int[] SearchRange(int[] nums, int target) {
var leftBorder = GetLeftBorder(nums, target);
var rightBorder = GetRightBorder(nums, target);
if (leftBorder == -2 || rightBorder == -2) {
return new int[] {-1, -1};
}
if (rightBorder - leftBorder >=2) {
return new int[] {leftBorder + 1, rightBorder - 1};
}
return new int[] {-1, -1};
}
public int GetLeftBorder(int[] nums, int target){
var left = 0;
var right = nums.Length - 1;
var leftBorder = -2;
while (left <= right) {
var mid = (left + right) / 2;
if (target <= nums[mid]) {
right = mid - 1;
leftBorder = right;
}
else {
left = mid + 1;
}
}
return leftBorder;
}
public int GetRightBorder(int[] nums, int target){
var left = 0;
var right = nums.Length - 1;
var rightBorder = -2;
while (left <= right) {
var mid = (left + right) / 2;
if (target >= nums[mid]) {
left = mid + 1;
rightBorder = left;
}
else {
right = mid - 1;
}
}
return rightBorder;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def getRightBorder(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
rightBorder = -2 # Record the case where rightBorder is not set
while left <= right:
middle = left + (right-left) // 2
if nums[middle] > target:
right = middle - 1
else: # Search for the right boundary; update left when nums[middle] == target
left = middle + 1
rightBorder = left
return rightBorder
def getLeftBorder(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
leftBorder = -2 # Record the case where leftBorder is not set
while left <= right:
middle = left + (right-left) // 2
if nums[middle] >= target: # Search for the left boundary; update right when nums[middle] == target
right = middle - 1
leftBorder = right
else:
left = middle + 1
return leftBorder
leftBorder = getLeftBorder(nums, target)
rightBorder = getRightBorder(nums, target)
# Scenario 1
if leftBorder == -2 or rightBorder == -2: return [-1, -1]
# Scenario 3
if rightBorder -leftBorder >1: return [leftBorder + 1, rightBorder - 1]
# Scenario 2
return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Solution 2
# 1. First, perform a binary search for the target in the nums array.
# 2. If the binary search fails, binarySearch will return -1, indicating that the target is not in nums. In this case, searchRange should return [-1, -1] directly.
# 3. If the binary search succeeds, binarySearch returns the index of one occurrence of the target in nums. Then, find the range by shifting pointers left and right.
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
while left<=right: # Constant: closed interval on both ends
middle = left + (right-left) // 2
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
return -1
index = binarySearch(nums, target)
if index == -1:return [-1, -1] # The target does not exist in nums, return [-1, -1]
# The target exists in nums, use pointers to find the applicable range
left, right = index, index
# Move left to find the left boundary
while left -1 >=0 and nums[left - 1] == target: left -=1
# Move right to find the right boundary
while right+1 < len(nums) and nums[right + 1] == target: right +=1
return [left, right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Solution 3
# 1. First, perform a binary search to find the first index that is greater than or equal to target (left boundary) and the first index that is greater than target (right boundary).
# 2. If the left boundary is less than or equal to the right boundary, return [left boundary, right boundary]. Otherwise, return [-1, -1].
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums:List[int], target:int, lower:bool) -> int:
left, right = 0, len(nums)-1
ans = len(nums)
while left<=right: # Constant: closed interval on both ends
middle = left + (right-left) //2
# If lower is True, execute the first part to find the first index greater than or equal to target; otherwise, find the first index greater than target
if nums[middle] > target or (lower and nums[middle] >= target):
right = middle - 1
ans = middle
else:
left = middle + 1
return ans
leftBorder = binarySearch(nums, target, True) # Search for the left boundary
rightBorder = binarySearch(nums, target, False) -1 # Search for the right boundary
if leftBorder<= rightBorder and rightBorder< len(nums) and nums[leftBorder] == target and nums[rightBorder] == target:
return [leftBorder, rightBorder]
return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Solution 4
# 1. First, perform a binary search to find the first index that is greater than or equal to target (left border).
# 2. Perform another binary search to find the first index that is greater than or equal to target+1, then subtract 1 to get the right border.
# 3. If the starting position is out of the array bounds or if the target doesn't exist, return [-1, -1]. Otherwise, return [left border, right border].
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
while left<=right: # Constant: closed interval on both ends
middle = left + (right-left) //2
if nums[middle] >= target:
right = middle - 1
else:
left = middle + 1
return left # If the target exists, return the first element equal to the target
leftBorder = binarySearch(nums, target) # Search for the left boundary
rightBorder = binarySearch(nums, target+1) -1 # Search for the right boundary
if leftBorder == len(nums) or nums[leftBorder]!= target: # Scenario 1 and Scenario 2
return [-1, -1]
return [leftBorder, rightBorder]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Rust
impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
let right_border = Solution::get_right_border(&nums, target);
let left_border = Solution::get_left_border(&nums, target);
if right_border == -2 || left_border == -2 {
return vec![-1, -1];
}
if right_border - left_border > 0 {
return vec![left_border, right_border - 1];
}
vec![-1, -1]
}
pub fn get_right_border(nums: &Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len();
let mut right_border: i32 = -2;
while left < right {
let mid = (left + right) / 2;
if nums[mid] > target {
right = mid;
} else {
left = mid + 1;
right_border = left as i32;
}
}
right_border as i32
}
pub fn get_left_border(nums: &Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len();
let mut left_border: i32 = -2;
while left < right {
let mid = (left + right) / 2;
if nums[mid] >= target {
right = mid;
left_border = right as i32;
} else {
left = mid + 1;
}
}
left_border as i32
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Go
func searchRange(nums []int, target int) []int {
leftBorder := getLeft(nums, target)
rightBorder := getRight(nums, target)
// Scenario 1
if leftBorder == -2 || rightBorder == -2 {
return []int{-1, -1}
}
// Scenario 3
if rightBorder - leftBorder > 1 {
return []int{leftBorder + 1, rightBorder - 1}
}
// Scenario 2
return []int{-1, -1}
}
func getLeft(nums []int, target int) int {
left, right := 0, len(nums)-1
border := -2 // Record border not set; cannot be -1, target = num[0], cannot distinguish scenario 1 and 2
for left <= right { // []closed interval
mid := left + ((right - left) >> 1)
if nums[mid] >= target { // Find the first equal to target
right = mid - 1
border = right
} else {
left = mid + 1
}
}
return border
}
func getRight(nums []int, target int) int {
left, right := 0, len(nums) - 1
border := -2
for left <= right {
mid := left + ((right - left) >> 1)
if nums[mid] > target {
right = mid - 1
} else { // Find the first greater than target
left = mid + 1
border = left
}
}
return border
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# JavaScript
var searchRange = function(nums, target) {
const getLeftBorder = (nums, target) => {
let left = 0, right = nums.length - 1;
let leftBorder = -2;// Record the case where leftBorder is not set
while(left <= right){
let middle = left + ((right - left) >> 1);
if(nums[middle] >= target){ // Search for the left boundary; update right when nums[middle] == target
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
const getRightBorder = (nums, target) => {
let left = 0, right = nums.length - 1;
let rightBorder = -2; // Record the case where rightBorder is not set
while (left <= right) {
let middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle - 1;
} else { // Search for the right boundary; update left when nums[middle] == target
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
let leftBorder = getLeftBorder(nums, target);
let rightBorder = getRightBorder(nums, target);
// Scenario 1
if(leftBorder === -2 || rightBorder === -2) return [-1,-1];
// Scenario 3
if (rightBorder - leftBorder > 1) return [leftBorder + 1, rightBorder - 1];
// Scenario 2
return [-1, -1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# TypeScript
function searchRange(nums: number[], target: number): number[] {
const leftBoard: number = getLeftBorder(nums, target);
const rightBoard: number = getRightBorder(nums, target);
// target on nums left or out of bounds
if (leftBoard === (nums.length - 1) || rightBoard === 0) return [-1, -1];
// target not in nums
if (rightBoard - leftBoard <= 1) return [-1, -1];
// target in nums
return [leftBoard + 1, rightBoard - 1];
};
// Find first index greater than target
function getRightBorder(nums: number[], target: number): number {
let left: number = 0,
right: number = nums.length - 1;
// 0 if target in nums left out of bounds
let rightBoard: number = 0;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] <= target) {
// Right boundary must be on the right (not including mid)
left = mid + 1;
rightBoard = left;
} else {
// Right boundary can be mid or left
right = mid - 1;
}
}
return rightBoard;
}
// Find first index less than target
function getLeftBorder(nums: number[], target: number): number {
let left: number = 0,
right: number = nums.length - 1;
// length-1 if target in nums right out of bounds
let leftBoard: number = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] >= target) {
// Left border must be on the left (not including mid)
right = mid - 1;
leftBoard = right;
} else {
// Left border can include mid or elements to the right
left = mid + 1;
}
}
return leftBoard;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Scala
object Solution {
def searchRange(nums: Array[Int], target: Int): Array[Int] = {
var left = getLeftBorder(nums, target)
var right = getRightBorder(nums, target)
if (left == -2 || right == -2) return Array(-1, -1)
if (right - left > 1) return Array(left + 1, right - 1)
Array(-1, -1)
}
// Find left boundary
def getLeftBorder(nums: Array[Int], target: Int): Int = {
var leftBorder = -2
var left = 0
var right = nums.length - 1
while (left <= right) {
var mid = left + (right - left) / 2
if (nums(mid) >= target) {
right = mid - 1
leftBorder = right
} else {
left = mid + 1
}
}
leftBorder
}
// Find right boundary
def getRightBorder(nums: Array[Int], target: Int): Int = {
var rightBorder = -2
var left = 0
var right = nums.length - 1
while (left <= right) {
var mid = left + (right - left) / 2
if (nums(mid) <= target) {
left = mid + 1
rightBorder = left
} else {
right = mid - 1
}
}
rightBorder
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Kotlin
class Solution {
fun searchRange(nums: IntArray, target: Int): IntArray {
var index = binarySearch(nums, target)
// Not found, return [-1, -1]
if (index == -1) return intArrayOf(-1, -1)
var left = index
var right = index
// Search for the left boundary
while (left - 1 >=0 && nums[left - 1] == target){
left--
}
// Search for the right boundary
while (right + 1 <nums.size && nums[right + 1] == target){
right++
}
return intArrayOf(left, right)
}
// Regular binary search
fun binarySearch(nums: IntArray, target: Int): Int {
var left = 0;
var right = nums.size - 1
while (left <= right) {
var middle = left + (right - left)/2
if (nums[middle] > target) {
right = middle - 1
}
else {
if (nums[middle] < target) {
left = middle + 1
}
else {
return middle
}
}
}
// Not found, return -1
return -1
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# C
int searchLeftBorder(int *nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
// Record when leftBorder is not set
int leftBorder = -1;
// Interval is [left, right]
while (left <= right) {
// Update middle value; equivalent to middle = (left + right) / 2
int middle = left + ((right - left) >> 1);
// If middle is target, set left border and continue leftward for other instances
if (nums[middle] == target) {
leftBorder = middle;
right = middle - 1;
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return leftBorder;
}
int searchRightBorder(int *nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
// Record when rightBorder is not set
int rightBorder = -1;
while (left <= right) {
int middle = left + ((right - left) >> 1);
// If middle is target, set right border and continue rightward for other instances
if (nums[middle] == target) {
rightBorder = middle;
left = middle + 1;
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return rightBorder;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int leftBorder = searchLeftBorder(nums, numsSize, target);
int rightBorder = searchRightBorder(nums, numsSize, target);
// Define return array and size
*returnSize = 2;
int *resNums = (int*)malloc(sizeof(int) * 2);
resNums[0] = leftBorder;
resNums[1] = rightBorder;
return resNums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Copyright © 2025 keetcoder