Introduction to algorithms with java-Search (Full search, Binary search)

Overview

This is a summary of the word "full search" that often appears when solving competitive programming. It's just my memo, but I hope it helps. From now on, we will add dynamic programming and Dijkstra's algorithm to the introduction to algorithms. A virtuous cycle in which the AtCoder rate increases as you write code examples. Basically, it just summarizes the knowledge gained on the net and Qiita.

I use java, which I'm used to, but anything is fine.

What is a full search?

As you can see from the name, I think that the whole search is to think about "all possible possibilities". It seems that there are various types, so let's consider problems and code examples for each type. The types of full search are as follows.

--Full search --Binary search (also known as binary search) --Depth-first search (also with DFS) --Breadth-first search (also known as BFS) --bit full search

For the time being, it seems good to know this much. Let's take a look at each one with an example.

Description of search algorithm and code example

I will explain each one.

Full search

Look up all possible answers by nesting for statements. It's easy. Let's look at an example. We will try to solve the simplest problems possible. It's easier to understand & because I can't solve it unless it's easy.

Example: AtCoder --abc144-b "81"

[Problem sentence](It's a little easier to write.) Since an integer N is given, determine whether N is the product of integers between 1 and 9, and output "Yes" if it can be expressed, and "No" if it cannot be expressed.

[Restrictions] 1 ≤ N ≤ 100, N is an integer

[Answer example]

main.java

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		//Flag for whether N meets the condition
		boolean flg = false;

		// i * j =I that becomes N,Search all for j
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				if (i * j == N) {
					flg = true;
					break;
				}
			}
			if (flg) {
				break;
			}
		}
		if (flg) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

It is like this. The for statement is doubly nested to search all the multiplication table patterns.

The caveat of full search is that ** the amount of calculation is large **. This time it was multiplication table, so in the worst case it was 9 ^ 2 = 81 loops, but if you were told that it was a product of multiplications up to 10 ^ 5 instead of multiplication table, for example, 10 ^ 5 * Note that it takes a lot of time to calculate 10 ^ 5 = 10 ^ 10.

Binary search

It's a way of repeating whether the things that apply are in the first half or the second half of the whole group. For example, let's say Mr. A asks, "What is my favorite number from 1 to 11?" Let's say Mr. A answers this question whether it is larger or smaller than the number you asked, or whether it is the answer. At this time, if it is a simple full search without thinking about anything, ask "1?" "2?" ... in order, and in the worst case, 11 times. I need a question. In terms of computational complexity, it is O (N) times.

If you do this with a binary search, it looks like the following. Let's say Mr. A's answer is 10.

Binary search example

1:you"(Between 1 and 11)Is it 6? "Mr. A" It's bigger than 6. "
2:you"(Between 6 and 11)Is it 9? "Mr. A" It's bigger than 9. "
3:you"(Between 9 and 11)Is it 10? "Mr. A" It's around. "

And, like this, you came up with the answer in just three questions. Starting from the value just in the middle of the group, each question determines whether there is an answer in the first half or the second half of the group. The figure below may be helpful. The range is halved for each question, so if you have only 11 candidates, you will find that you only need 4 questions (2 ^ 4 = 16) at most. Is it O (logN) in terms of computational complexity? Let's go to the example.

Example: AtCoder --abc146-c "Buy an Integer"

Problem sentence Takahashi went to an integer store to buy one integer.

Integers from 1 to 10 ^ 9 are sold at integer stores, and to buy integer N A × N + B × d (N) Yen is required. Where d (N) is the number of digits in decimal notation for N. When Takahashi-kun's money is X yen, find the largest integer that Takahashi-kun can buy. However, if there are no integers you can buy, output 0.

[Restrictions] All inputs are integers. 1≤A≤10^9 1≤B≤10^9 1≤X≤10^18

[Answer example]

main.java

import java.util.Scanner;

public class Main {

	static long A;
	static long B;
	static long X;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		A = sc.nextLong();
		B = sc.nextLong();
		X = sc.nextLong();

		long max = 1000000000l + 1l;
		long min = 0l;

		//Binary search
		for (;;) {
			//2 Mean of numbers
			long mid = (max + min) / 2;
			if (canSolve(mid)) {
				//If you can solve with the average value, search in the latter half
				min = mid;
			} else {
				//If you can't solve with the average value, search in the latter half
				max = mid;
			}

			if (max - min <= 1) {
				//Binary search end
				break;
			}
		}

		System.out.println(min);

	}

	//Get the number of digits
	static long len(long num) {
		return String.valueOf(num).length();
	}

	//Whether it can be solved
	static boolean canSolve(long num) {
		return A * num + B * len(num) <= X ? true : false;
	}
}

Of course, if you try to solve this problem with a simple full search, you have to think about all N, and since N is an integer between 1 and 10 ^ 9, in the worst case, it is processed 10 ^ 9 times. Must be. That's why binary search is here. Can you see it by looking at the code?

long max = 1000000000l + 1l; This is a little difficult place. Decimal numbers are truncated when dividing java long, so if max is set to 1,000,000,000, When min: 999,999,999 and max: 1,000,000,000, mid becomes 999,999,999 (= min), and it becomes impossible to check 1,000,000,000.

Also, I simply like the ease of viewing and the method division, so I'm not sure if I can get the number of digits and buy it, but either one is fine.

I solved this problem with a binary search, but I think the advantage is that the amount of calculation is small. In the worst case of this problem, you can reach the answer by looping about 30 times. Because 2 ^ 30 is greater than 10 ^ 9.

However, it seems better to keep in mind that binary search is only useful for "sorted populations". I feel that a binary search can be used for "continuous integers".

I studied and explained about full search and binary search, but how was it? I thought I would do the same article for depth-first search, breadth-first search, and bit full search, but later I thought it would be difficult to look back, so I decided to post the articles separately. Next time, I will study and explain about depth-first search and breadth-first search. looking forward to.