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

This article mainly introduces what is the dichotomy in C++, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article. Let the editor take you to know it.

One, integer dichotomy

The relationship between monotonicity and dichotomy: if there is monotonicity, it must be dichotomous, and using dichotomy is not necessarily monotonous. The essence of dichotomy is not monotonicity but boundary point (find the minimum or maximum number that meets the condition) integer dichotomy is to find the right endpoint of the red range or the left endpoint of the green range.

1. The integer binary template bool check (int x) {/ *... * /} / / checks whether x satisfies some property / / interval [l, r] is divided into [l, mid] and [mid + 1, r]: int bsearch_1 (int l, int r) {while (l)

< r) { int mid = l + r >

If (check (mid)) r = mid; / / check () to judge whether mid satisfies the property else l = mid + 1;} return l;} / / interval [l, r] is divided into [l, mid-1] and [mid, r] use: int bsearch_2 (int l, int r) {while (l)

< r) { int mid = l + r + 1 >

> 1; if (check (mid)) l = mid; else r = mid-1;} return l;}

[template 1]

1. Find the red boundary point

Note: + 1 reason:

/ is rounded down, when the difference between l and r is only 1, that is, l = r-1, the final result mid = l (that is, the result remains the same or l), mid = r after adding 1, and l = r after the cycle again, that is, [r, r], finally ends the cycle. If you don't make up 1, there will be an endless cycle.

[template 2]

Find the green boundary point

two。 The idea of solving the dichotomy problem

Each time, first divide the interval, write a mid, and then consider whether to add 1 operation and then think about a check () function, whether Kangkang satisfies the property, according to the value of the check () function to determine how to divide (which side is mid), whether it is l = mid, or r = mid, the first kind can add 1. (the key is to find the property, determine whether the property is satisfied, and then determine whether the mid is on the left or right.)

3. Practice

(1)。 The range of numbers

Given an array of integers of length nn in ascending order, and qq queries.

For each query, the start and end positions of an element kk are returned (positions are counted from 00).

If the element does not exist in the array,-1-1 is returned.

Input format

The first line contains integers n and Q, indicating the length of the array and the number of queries.

The second line contains nn integers (all in the range of 1 ∼ 10000), representing the complete array.

The next Q line, each containing an integer k, represents a query element.

Output format

A total of Q lines, each containing two integers that represent the start and end positions of the element being sought.

If the element does not exist in the array,-1-1 is returned.

Data range

1 ≤ n ≤ 100000

1 ≤ q ≤ 10000

1 ≤ k ≤ 10000

Enter a sample:

6 31 2 2 3 3 4345

Sample output:

3 45 5-1-1

Train of thought:

[reference Code]

# includeusing namespace std;const int N = 1000000 characters 10 int int Q [N]; int main () {int n, m; cin > > n > > m; for (int I = 0 Ten I)

< n; i++) cin>

> Q [I]; while (Mmura -) {int x; cin > > x; / / find the starting position int l = 0, r = n-1; while (l

< r) { int mid =(l + r)/2; if(q[mid] >

= x) r = mid; else l = mid + 1;} if (Q [l]! = x) coutd; / / enumerate the root for (int I =-100; I eps) {/ / x1

< x，f(x1)×f(x2) Y) r = mid; else l = mid; } return mid;}int main(){ double Y; while(~scanf("%lf", &Y)){ if(Y < 6 || Y >

677269824) puts ("None"); else printf ("% .4f\ n", erfen (Y));} return 0;} Thank you for reading this article carefully. I hope the article "what is dichotomy in C++" shared by the editor will be helpful to you. At the same time, I hope you will support us, pay attention to the industry information channel, and more related knowledge is waiting for you to learn!

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.