# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.# Introduction

Typically search problems ask for the number of combinations or the maximum or minimum value of a parameter. A search problem is very similar to an implementation problem.

# Examples

## Example 1

Given an array a of N integers, find the largest number.

This is likely one of the most primitive search problems. It requires you to *search* the whole array. Use a variable to hold the current maximum element and update as necessary.

### Implementation

### Time complexity

\mathcal{O}(N)

## Example 2

Given a number N, determine if it is prime.

Another simple search problem. In this problem, you are searching for a prime factor of N. Just one prime factor (other than N) is enough to disprove the number prime. So you can try all numbers below N and check divisibility, breaking when if one found.

However, we can optimize the search. All prime factors of a number N are less than or equal to \sqrt{N}. This is because a composite number has at least two prime factors. As one factor grows, the other one shrinks. To maximize \min(a, b), where a and b are factors of N, they have to be as closest to \sqrt{N} as possible. Thus, you only have to check all numbers less than \sqrt{N}.

### Implementation

### Time complexity

\mathcal{O}(\sqrt{N})

# Conclusion

Most searches problems aren’t as simple as the example problems above. Some may require complex handling of states, using techniques such as recursion. The ability to figure out optimizations is important. It helps to eliminate repeated states. With operations such as rotation and switches, it helps to know that rotating it back to the start or switching something twice is the same as doing it zero times.

More complex types of searches include binary search, dynamic programming and graph theory.

# Practice

CCC ‘12 S3 - Absolutely Acidic

ECOO ‘16 Board P2 - Spindie

CCC ‘08 S2 - Pennies in the Ring

MWC ‘15 #5 P2: WildCard

CCC ‘09 S2 - Lights Going On and Off

CCC ‘08 S4 - Twenty-four