Shulou(Shulou.com)06/01 Report--

Editor to share with you how Leetcode search insertion location, I believe that most people do not know much, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

Topic description:

Given a sorted array and a target value, find the target value in the array and return its index. If there is no target value, it is assumed that it is inserted into the corresponding position of the array and the index of that position is returned (assuming the array has no duplicates)

For example: input: [1,3,5,6] 5out:2

Input: [1, 3, 5, 6] 2out:1input: [1, 3, 5, 6] 7out:4

This article is supported by "one partner Editor".

The first attempt

Array: nums

Target value: target

Traversing the array from left to right returns the current index value I when nums [I] = = target. When nums [I] > target, there is no target value in the array, and target should be inserted at I right now, so the index value is also I.

Nums [I] = = target: returns the index value I

Nums [I] > target: also returns the index value I

The speed is not fast.

Optimization algorithm-binary search

Once there was a sketch: Qizhi and the soldier went to see a doctor. The doctor asked him to do a comprehensive examination of his heart, liver, spleen, lungs and kidneys, and finally told him that you had a cold. Although this is a joke, it also reflects a kind of divide-and-conquer thinking.

Dichotomy idea (subtraction): divide [search area] into [including target area] and [without target area], constantly eliminate [excluding target area], and finally leave [including target area]

Binary search algorithm:

Use three cursors: left, right and mid to continuously narrow the range.

There are two questions to think about when using the binary search algorithm

(1) return right or left

(2) how to set the boundary of the area

This article is supported by "one partner Editor".

The practice of this question:

Set three parameters: left, right and mid

When the loop condition is while lefttarget: right = mid-1

(3) mid

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.