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

leetcode Portal

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 ：

1. Find the first element whose value is equal to the given value
2. Find the last element whose value is equal to the given value
3. Find the first element greater than or equal to the given value
4. Find the last element less than or equal to the given value

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

step

1. Find the subscript of the first element whose value is equal to the given value
2. Find the subscript of the last element whose value is equal to the given value
3. 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