Part 1: Basic Concepts

1.1What is Binary Search?

Binary search is an algorithm for quickly finding a target value in a sorted array. It rapidly locates the target by continuously halving the search range.

Basic Idea: Just like looking up a word in a dictionary:

• Open to the middle of the dictionary

• If the word to be searched is before the current page, continue searching in the first half

• If the word to be searched is after the current page, continue searching in the second half

• Repeat this process until the target is found

1.2 Time Complexity

For a sorted array containing n elements:

• Sequential Search: In the worst case, it requires n comparisons → O(n)

• Binary Search: The range is halved after each comparison → O(log₂n)

Specific Comparisons:

• n=1000: Sequential search requires at most 1000 comparisons, binary search requires at most 10 comparisons

• n=1000000: Sequential search requires at most 1 million comparisons, binary search requires at most 20 comparisons

• n=1 billion: Sequential search requires at most 1 billion comparisons, binary search requires at most 30 comparisons

Part 2: Basic Binary Search

Problem 1: Basic Binary Search (No Duplicate Elements)

Please use binary search to find the position of valuex in a sorted increasing array (no duplicate elements). If x does not exist in the array, please output -1!

Input Format

The first line contains an integern, representing the number of elements in the array (n <= 600000)

The second line containsn numbers, representing the n increasing elements of the array (1<= element value <= 2000000)

The third line contains an integerx, representing the number to be searched (0<=x<=2000000)

Output Format

Output the position as required or-1.

Input/Output Example 1

Input:

10

1 3 5 7 9 11 13 15 17 19

3

Output:

2

Problem Analysis:

• Input: A sorted increasing array with no duplicate elements

• Goal: Find the position of a specific element

• Output: Return the position if found (counting from 1), return -1 if not found

Detailed Solution Approach:

1. Initialize Boundaries:<span>L=0, R=n+1</span>, thus the search interval is (L,R]

2. Loop Condition:<span>while(L+1 < R)</span>, ensuring there are at least two elements in the interval

3. Calculate Midpoint:<span>mid = (L+R)/2</span>, note that integer division rounds down

4. Comparison Judgment:

• Equal: Return position directly

• Target value larger: Continue searching in the right half

• Target value smaller: Continue searching in the left half

Code Step-by-Step Analysis:

#include<bits/stdc++.h>using namespace std;
int n,a[100005],x;
int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    // Store array starting from index 1    scanf("%d",&x);
    int L=0,R=n+1,mid;        // Step 1: Initialize boundaries    while(L+1<R){             // Step 2: Loop condition        mid=(L+R)/2;          // Step 3: Calculate midpoint        if(a[mid]==x){            cout<<mid;        // Step 4: Output position            return 0;        }        else if(a[mid]<x)     // Step 5: Comparison condition            L=mid;        else            R=mid;    }    cout<<-1;    return 0;}

Key Points Explanation:

• Why<span>L=0, R=n+1</span>? This ensures the search interval includes all elements

• Why<span>while(L+1<R)</span>? The loop stops when L and R are adjacent

• Why adjust boundaries directly<span>L=mid</span> or <span>R=mid</span>? Because we are using a left-open right-closed interval

Instance Demonstration: Searching for the number 3 in the array<span>[1,3,5,7,9,11,13,15,17,19]</span>

• Initial: L=0, R=11

• First Round: mid=5, a[5]=9 > 3 → R=5

• Second Round: mid=2, a[2]=3 == 3 → Found, output 2

Part 3: Binary Search with Duplicate Elements

2.1 Find Left Boundary (First Occurrence Position)

Please use binary search in a sorted non-decreasing array (with equal values) to find the first occurrence position of valuex. If x does not exist, please output -1.

Please note: This problem requires findingq occurrences of x, each at the first occurrence position in the array.

For example, if there are6 numbers: 1 2 2 2 3 3, and if we want to find the first occurrence positions of 3 numbers: 3 2 5, the answers are: 5 2 -1.

Input Format

The first line contains an integern, representing the number of elements in the array (n <= 10^5)

The second line containsn integers separated by spaces, representing the n elements of the array (1<= element value <= 10^8)

The third line contains an integerq, representing the number of queries for the first occurrence positions (q <= 10^5)

The fourth line containsq integers separated by spaces, representing the numbers to be searched (1<= number to be searched <= 10^8)

Output Format

Output one line containing q integers, indicating the first occurrence positions of each number in the array. If such a number does not exist, please output -1.

Input/Output Example 1

Input:

6

1 2 2 2 3 3

3

3 2 5

Output:

5 2 -1

Problem Characteristics:

• The array contains duplicate elements

• Need to find the first occurrence position of the target value

• If it does not exist, return -1

Solution Approach: Use an improved binary search framework, when the target value is found, continue searching to the left for an earlier occurrence

Core Algorithm:

int find(int x){    int L=0,R=n+1;    while(L+1<R){              // Step 1: Loop condition        int mid=(L+R)/2;        if(a[mid]>=x)          // Step 2: Condition judgment            R=mid;            // Found the position >=x, continue searching to the left        else            L=mid;            // Search to the right    }    return R;}

Instance Analysis: Find the first occurrence of the number 2 in the array<span>[1,2,2,2,3,3]</span>

• Initial: L=0, R=7

• First Round: mid=3, a[3]=2 >= 2 → R=3

• Second Round: mid=1, a[1]=1 < 2 → L=1

• Third Round: mid=2, a[2]=2 >= 2 → R=2

• Loop ends, return R=2 (correct position)

Complete Code:

2.2 Find Right Boundary (Last Occurrence Position)

Please use binary search in a sorted non-decreasing array (with equal values) to find the last occurrence position of valuex. If x does not exist, please output -1.

For example, if there are6 numbers: 1 2 2 2 3 3, and if we want to find the last occurrence positions of 3 numbers: 3 2 5, the answers are: 6 4 -1.

Input Format

The first line contains an integern, representing the number of elements in the array (n <= 10^5)

The second line containsn integers separated by spaces, representing the n elements of the array (1<= element value <= 10^8)

The third line contains an integerq, representing the number of queries for the last occurrence positions (q <= 10^5)

The fourth line containsq integers separated by spaces, representing the numbers to be searched (1<= number to be searched <= 10^8)

Output Format

Output one line containing q integers, indicating the last occurrence positions of each number in the array. If such a number does not exist, please output -1.

Input/Output Example 1

Input:

6

1 2 2 2 3 3

3

3 2 5

Output:

6 4 -1

Solution Approach: Use the left boundary search function to find the left boundary of x+1, then subtract 1 to get the last position of x

Mathematical Principle:

• The first position greater than x = find(x+1)

• The last position of x = find(x+1) – 1

Complete Code:

Instance Verification: Find the last position of the number 2 in the array<span>[1,2,2,2,3,3]</span>

• find(2+1) = find(3) = 5 (the first position >=3)

• Last position = 5-1 = 4 (correct)

Part 4: Detailed Applications of Binary Search

Application 1: Count Elements Less Than a Certain Value

Problem: The River Challenge

Problem Description

There is a triathlete whose weakness is swimming, and there are n rivers with different flow rates next to his house. He wants to train for m days.

During these m days, he has different stamina each day, and he can only swim in rivers with flow rates less than his stamina, otherwise he will be swept away to the Pacific Ocean (?!).

He wants to know how many rivers he can swim in each day.

Input Format

One line, two integers n and m. 1 ≤ n, m ≤10⁵

Output Format

m lines, each line contains an integer indicating the number of rivers.

Input/Output Example 1

Input Data 1

10

1 1 1 2 2 2 2 3 4 4

5

3

2

5

4

1

Output Data 1

7

3

10

8

0

Problem Analysis:

• Given a value x, count the number of elements in the array that areless than x.

• This is equivalent to finding the first positiongreater than or equal to x, all elements before this position are less than x

Mathematical Relationship:

• The number of elements less than x = find(x) – 1

Code Implementation:

Instance: Array<span>[1,2,2,2,3,3]</span>, x=3

• find(3) = 5 (the first position >=3)

• The number of elements less than 3 = 5-1 = 4 (elements: 1,2,2,2)

Application 2: Count Elements Within a Range

Problem: Heaven_Pearl

I have many (n magical pearl necklaces… (actually, fairies love beauty more than mortals), every day I have to pick one to wear… Choosing which one is very particular; if it is uglier than my rival, I will be… If it is prettier than the queen, then I’m doomed… So I hope you can help me solve this headache— count how many necklaces I can wear each day.

Input Format

The first line contains a positive integern (the total number of necklaces).

The second line containsn integers (representing the beauty level of each necklaceX_i, 0<=X_i<=maxlongint).

The third line contains a positive integerm, representing the total number of days (i.e., total queries).

For the nextm lines, each line contains two integersA_i, B_i (1<=A_i, B_i<=maxlongint), querying the number of necklaces with beauty levels betweenA_i and B_i (inclusive, the relationship between A_i and B_i is uncertain).

Output Format

Outputm lines, for each query output a line, indicating the number of necklaces with beauty levels betweenA_i and B_i (inclusive).

Input/Output Example 1

Input:

7

82 3 5 6 7 7

6

15

86

110

55

44

78

Output:

3

4

7

1

0

3

Sample Explanation

For 25% of the data, m,n<=1000. For 100% of the data, m,n<=100000.

Problem Analysis:

• Count the number of elements within the range [x,y]

• Need to find the first position >=x and the first position >y

Mathematical Relationship:

• The number of elements in the range [x,y] = find(y+1) – find(x)

Code Implementation:

Instance: Array<span>[1,2,2,2,3,3]</span>, range [2,3]

• find(2) = 2 (the first position >=2)

• find(3+1) = find(4) = 6 (the first position >=4)

• The number of elements in the range = 6-2 = 4 (elements: 2,2,2,3,3)

Application 3: Count Pairs with a Fixed Distance

Problem: Bluetooth Connection

n individuals are lining up to sign in, the sign-in location is at0, the distance of theith individual from the sign-in location isp_i. Lining up is boring, so they can connect via Bluetooth with nearby people, the effective distance of the Bluetooth signal is limited, and each person can only connect with those within a distance ofd. Given the position of each person and the effective distance of Bluetoothd, please program to calculate how many pairs can chat with each other.

Input Format

The first line contains an integern. (2≤n≤1000000)

The second line contains an integerd. (0≤d≤1000000)

Next, there aren lines, each containing an integerp_i (0≤p_i≤1 000 00000), representing the distance of each individual from the sign-in location.

Output Format

An integer indicating how many pairs can chat with each other in the queue.

Input/Output Example 1Input:

Input:

5

6

13 5 11 34

Output:

4

Sample Explanation

Sample Explanation: In the queue1 and 5, 1 and 3, 5 and 11, 3 and 5, a total of4pairs can chat with each other.

[Data Range]

For 100% of the data,1≤n≤1000000

Problem Analysis:

• For each person, count the number of people within a distance of d

• For position a[i], the range of positions that satisfy the condition is [a[i], a[i]+d]

Mathematical Relationship:

• For the i-th person, the number of people they can connect with is: find(a[i]+d+1) – 1 – i

Code Implementation:

Instance Verification: Positions<span>[1,3,5,11,34]</span>, d=6

• The first person (1): can connect to people before position 7 → 3 people

• The second person (3): can connect to people before position 9 → 3 people

• The third person (5): can connect to people before position 11 → 2 people

• The fourth person (11): can connect to people before position 17 → 1 person

• The fifth person (34): can connect to people before position 40 → 0 people

• Total pairs = 3+3+2+1+0 = 9, but the problem outputs 4 (need to confirm calculation method)

Application 4: Count Pairs with a Fixed Difference

Problem: Difference

Nannan is solving problems online and finds the first problem: finding the sum of two numbers(A+B Problem) too boring, so he adds a problem: A-B Problem, which confuses many kids, haha.

The problem is as follows: Given N sorted integers, a difference C, find two numbers A and B in these N integers such that A-B=C, and ask how many such solutions exist? For example:

N=5, C=2, the 5 integers are: 2 2 4 8 10. The answer is 3.

Specific solutions: The third number minus the first number; the third number minus the second number; the fifth number minus the fourth number.

Input Format

The first line contains 2 positive integers: N,C.

The second line contains N integers: already sorted. Note: there may be duplicates.

Output Format

An integer indicating the total number of pairs (A,B) such that A-B=C.

Input/Output Example 1

Input:

4 1

1 1 2 2

Output:

4

Sample Explanation

For the 5 data: N ranges from [1…1,000]. For all data: N ranges from [1…100,000]. C ranges from [1…1,000,000,000]. Each number in N ranges from [0…1,000,000,000].

Problem Analysis:

• For each a[i], count the occurrences of a[i]+C

• Use binary search twice to find the first and last occurrence positions of a[i]+C

Code Implementation:

Instance: Array<span>[1,1,2,2]</span>, C=1

• For 1: 1+1=2 appears 2 times

• For 1: 1+1=2 appears 2 times

• For 2: 2+1=3 appears 0 times

• For 2: 2+1=3 appears 0 times

• Total number of solutions = 2+2+0+0 = 4

Part 5: Comprehensive Applications

Problem: Valid Solutions

Inputn positive integers, find the number of ways to select one or two such that their sum is less than or equal tok.

Input Format

The first line contains two integersN and K (1<=N<=100 000 , 1<=K<=100000000).

The second line contains N integers. Each integer is less than or equal to100000000.

Output Format

Output the number of valid solutions.

Input/Output Example 1Input:

Input:

9 8

1 2 5 4 3 9 6 7 8

Output:

20

Sample Explanation

[Data Range]1<=N<=100 000 , 1<=K<=100000000 , each integer is less than or equal to 100000000.

Problem Analysis:

Count the number of ways to select one or two elements such that their sum is less than or equal to k.

Solution Approach:

1. Select one: All single elements ≤k are valid

2. Select two: For each a[i], find the largest j such that a[i]+a[j]≤k

Code Implementation:

Instance Verification: Array<span>[1,2,3,4,5]</span>, k=4

• Select one: 1,2,3,4 are valid → 4 valid

• Select two:

• 1 can pair with 2,3 → 2 valid

• 2 can pair with 2 → 1 valid

• Other combinations exceed 4

• Total valid solutions = 4+2+1 = 7

Problem: Selecting Cows

On a coordinate axis, there are N cows, the position of theith cow isX_i. FJ now wants to select three cows for a competition, assuming he selects cowsa,b,c. Then the following conditions must be met:

1. X_a < X_b < X_c.

2. X_b-X_a <= X_c – X_b <= 2 * (X_b – X_a).

Your task is to calculate how many different selections there are.

Input Format

The first line contains an integerN. (3 <= N <= 1000)

Next, there are N lines, the i-th line contains an integerX_i.

Output Format

An integer.

Input/Output Example1

Input:

5

3

1

10

7

4

Output:

4

Sample Explanation

There are4 different selections, each corresponding to the coordinates of the three cows: {1, 3, 7} {1, 4, 7} {4, 7, 10} {1, 4, 10}

Problem Analysis: Select triplets (a,b,c) that satisfy:

1. X_a < X_b < X_c

2. X_b-X_a ≤ X_c-X_b ≤ 2*(X_b-X_a)

Solution Approach: Fix a and b, c needs to satisfy:

• X_c ≥ X_b + (X_b-X_a)

• X_c ≤ X_b + 2*(X_b-X_a)

Code Implementation:

Part 6: Summary and Techniques

Three Modes of Binary Search

1. Exact Search: Search for elements equal to the target value

while(L+1<R){    mid=(L+R)/2;    if(a[mid]==x) return mid;    else if(a[mid]<x) L=mid;    else R=mid;}

1. Left Boundary: Search for the first element equal to the target value

while(L+1<R){    mid=(L+R)/2;    if(a[mid]>=x) R=mid;    else L=mid;}

1. Right Boundary: Search for the last element equal to the target value

// Use left boundary search return find(x+1)-1;

Common Problems and Solutions

Problem Type	Solution	Core Code
Count elements less than x	find(x)-1	<span>cnt = find(x)-1</span>
Count elements in the range [x,y]	find(y+1)-find(x)	<span>cnt = find(y+1)-find(x)</span>
Count elements equal to x	find(x+1)-find(x)	<span>cnt = find(x+1)-find(x)</span>
Find the closest element to x	Compare find(x) and find(x)-1	<span>min(abs(a[pos]-x), abs(a[pos-1]-x))</span>

Debugging Techniques

1. Print Intermediate Processes:

while(L+1<R){    mid=(L+R)/2;    cout<<"L="<<L<<", R="<<R<<", mid="<<mid<<", a[mid]="<<a[mid]<<endl;    // ... other code}

1. Verify Boundary Conditions:

• Empty array case

• Only one element case

• Target value less than all elements

• Target value greater than all elements

• Target value does not exist but is between some elements

1. Test Case Design:

• Small data tests: Manually verify correctness

• Large data tests: Verify time efficiency

• Boundary tests: Test various extreme cases

Learning Suggestions

1. Understand the Principles: Do not memorize code, understand how each binary search reduces the search range

2. Draw Diagrams: Draw the array and search process on paper to help understanding

3. Progress Gradually: Start with basic binary search, gradually learn various variants

4. Practice a Lot: Binary search requires a lot of practice to master

Thank you for reading

END