There's nothing in this series , It's pure leetcode Topic analysis , Don't seek to use a coquettish line or niche solution , But with clear code and simple enough ideas to help you clear up the topic . Let you no longer be afraid of the written test in the interview .

## 24. Find the first and last positions of the elements in the sort array (find-first-and-last-position-of-element-in-sorted-array)

### label

- Two points search
- secondary

### subject

There's no point here ,leetcode Just open it , The main idea of the topic ：

Give a ** Orderly ** Array nums And a number target, It is required to find the first element subscript equal to this element in the array , The last element subscript equal to this element .

### The basic idea

See ascending order , Ordered arrays think of binary search

Look at this article Two points search

This is a classic binary search variant . Binary search has 4 Big basic variety problem ：

- Find the first element whose value is equal to the given value
- Find the last element whose value is equal to the given value
- Find the first element greater than or equal to the given value
- Find the last element less than or equal to the given value

We use the front 2 Variety , Merger will solve the problem .

### step

- Find the subscript of the first element whose value is equal to the given value
- Find the subscript of the last element whose value is equal to the given value
- combined

### The writing method realizes

Looking at the long , It's really simple , Don't panic.

```
// Dichotomous search for the first and target Equal elements , Time complexity O(logn)
let searchFirstEqualElement = (nums, target) => {
let [left, right] = [0, nums.length-1]
while (left <= right) {
pivot = left + Math.floor((right - left) / 2)
if (nums[pivot] > target) {
right = pivot - 1
} else if (nums[pivot] < target) {
left = pivot + 1
} else {
// All of the above is the basic code of binary search , As like as two peas
// The difference is equal to , We want to find the first one with target Equal elements
if ((pivot === 0) || (nums[pivot-1] !== target)) {
// When these two things happen, we find 『 Left boundary 』
// 1. index be equal to 0, There's nothing to say
// 2. When nums[pivot-1] One more element on the left doesn't equal target It means we've reached the left border
return pivot
}
// Or move to the right and left , That is the pivot look forward
right = pivot - 1
}
}
return -1
}
// Binary search for the last one and target Equal elements , Time complexity O(logn)
let searchLastEqualElement = (nums, target) => {
let [left, right] = [0, nums.length-1]
while (left <= right) {
pivot = left + Math.floor((right - left) / 2)
if (nums[pivot] > target) {
right = pivot - 1
} else if (nums[pivot] < target) {
left = pivot + 1
} else {
// All of the above is the basic code of binary search , As like as two peas
// The difference is equal to , We want to find the last one with target Equal elements
if ((pivot === nums.length-1) || (nums[pivot+1] != target)) {
// When these two things happen, we find 『 Right border 』
// There's a way of doing that , I don't want to repeat this
return pivot
}
left = pivot + 1
}
}
return -1
}
// Finally, just merge
var searchRange = function(nums, target) {
return [searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)]
};
console.log(searchRange([5,7,7,8,8,10], 8))
Copy code
```

in addition , If you can't remember how to write two points in the interview , Forced writing is OK , The realization is the most important .

That's OK. , Notice that you're using js, Make good use of tools , It's also ability .

Efficient answers > Write out > I can't write

```
let searchRange = (nums, target) => {
return [nums.indexOf(target), nums.lastIndexOf(target)]
};
Copy code
```

There is not much time today , Just one

In addition, I'd like to recommend this elder brother's article to you , It's very simple , It is very useful for advanced students , Wall crack recommendation ！！！ Core concepts and algorithms

That's all for today , If you want to brush the topic with me, you can add my wechat Search my wechat `infinity_9368`

, You can chat and say Add my code " Heavenly King Gedi tiger " The next sentence is ` english `

, Please send me the verification message `presious tower shock the rever monster`

, I see it through , The code is not right, no, No , After that, I'll do my best to help you , But pay attention to the way you ask questions , I suggest you read this article first ： The wisdom of asking questions