Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

When you learn an algorithm, you should start with something simple, keep practicing, and break through one by one

dichotomy

Dichotomy in the interview will often encounter handwriting algorithm, we need to complete the handwriting out, and no error! Let’s write a binary search

There are ordinary binary search methods and more difficult binary variant methods. Dichotomy reduces the scope of the problem by constantly comparing operations, so as to find the final answer, which is also the embodiment of divide-and-conquer thought.

Little chestnut LeetCode 167

LeetCode 167: Ordered array of integers (target)

So you can use the loop of violence, the direct traversal, and of course, as a programmer, that’s not an elegant way to do it. When we see the word order here, we have to think of dichotomy!

Title description:

  1. Sum of two numbers II – Enter an ordered array

Given an array of integers in non-decreasing order numbers, find two numbers that add up to the target number. The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.

You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 equals the target number 9. So index1 = 1, index2 = 2.

Here’s what we need to note:

  • Return the index of the target element, not the index. Indexes start at 1 and subscripts start at 0

The interview may not be as complete as described above, so check with the interviewer during the interview to confirm some questions

  • What if there’s no solution? Ensure that there is solution
  • How many solutions are there?
  • Return any solution? Are there any requirements on the return order?

答 案 :

1. Direct violence:

Two-level traversal: Solve the problem first and optimize it later (but on LeetCode it should time out!) ; This method also doesn’t use the order feature in the problem: O(n^2).

2. Order, we think of binary search

The colliding pointer is also used here

  • Let’s look at the execution time and the results

  • Solution code:

/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
var twoSum = function (numbers, target) {
  let l = 0,
    r = numbers.length - 1 // Define two Pointers squeezed from both ends of the array (lookup)
  while (l < r) {
    // Can the details be equal to?
    let m = numbers[l] + numbers[r]
    if (m > target) {
      r--
    }
    if (m < target) {
      l++
    }
    if (m === target) return [l + 1, r + 1]}}Copy the code

thinking

Dichotomy is usually used to find structures such as ordered arrays. When it comes to keyword order or lookup, we can think of a solution using dichotomy. Use element associations to gradually reduce the size of the problem.

reference

  • Go straight to LeetCode title: 167