Written test programming (I) | binary search and array correlation

Recently, a small buddy has to prepare some interview related articles in the background of the official account. Actually, I intend to prepare for the interview related articles. After the Spring Festival, the author will prepare some interview questions for job interviews related to the field of big data, and share some interview experience, hoping to help you.

Today, let's share some programming problems often encountered in the written test, including problem-solving ideas and code implementation. The following figure is the outline of this sharing:

Binary search method

Binary search, also known as half search, is an efficient search method. Premise: (1) sequential storage structure must be adopted (2) keywords must be arranged in order

Principle: divide the array into three parts, Followed by the median (the so-called median is the value in the middle of the array) before, after and after the median, compare the value to be found with the median of the array. If it is less than the median, find it in front of the median. If it is greater than the median, find it behind the median and return it directly when it is equal to the median. Then, there is a recursive process in turn, which continues to decompose the first half or the second half into three parts.

Common array related programming problems

1. Decompose positive integers into prime factors

2. Quickly find the missing number in a given integer array from 1 to 100

3. Sort the numbers in the string in positive order, and the position of the letters in the string remains unchanged

4. Find the largest and smallest numbers in an unordered integer array

5. In an integer array, find all pairs of numbers and satisfy that their sum is equal to a given number

6. If an array contains multiple duplicate elements, find these duplicate numbers

7. The Java implementation removes duplicate elements from a given array

8. Java implements array inversion

Focus on WeChat official account: big data learning and sharing, get more technical dry cargo