[BaekJun, C++] 1920: finding numbers

 https://www.acmicpc.net/problem/1920


#include <iostream> #include <algorithm> // for sorting using namespace std; const int MAX_SIZE = 100000; int binarySearch(int arr[], int low, int high, int target) { while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return 1; // Element found else if (arr[mid] < target) low = mid + 1; else high = mid - 1; } return 0; // Element not found } int main() { // Input the size of the first array int n; cin >> n; // Dynamic allocation of memory for the first array int* numbers = new int[n]; // Input elements for the first array for (int i = 0; i < n; i++) { cin >> numbers[i]; } // Sort the array (required for binary search) sort(numbers, numbers + n); // Input the size of the second array int m; cin >> m; // Input elements for the second array int* finding = new int[m]; // Check if each element in the second array is present in the first array using binary search for (int i = 0; i < m; i++) { cin >> finding[i]; cout << binarySearch(numbers, 0, n - 1, finding[i]) << endl; } // Deallocate dynamically allocated memory delete[] numbers; delete[] finding; return 0; }


The operation of the main function is simple.

When an integer M is received, allocate an array of size M.

When an integer N is received, allocate an array of size N.

After that, to check if the integers in the array of size N are present in the array of size M, confirmation is done through binary search using the binarySearch() function.

Binary search involves receiving low and high values defining mid as (low + high) / 2.

Then, it checks whether mid is the integer we are looking for. If not, since the array was sorted before binary search, if the integer is in the earlier part, set high to mid - 1, and if it is in the later part, set low to mid + 1, and repeat the process.

I learned that performing sorting (O(nlogn)) followed by binary search (O(logn)) is more efficient than just searching from the beginning.

Comments

Post a Comment

Popular posts from this blog

[BaekJun, C++] 1018: Repainting a Chess Board

Image
  https://www.acmicpc.net/problem/1018 Problem Jimin found an M×N sized board in his mansion that is divided into MN unit squares. Some of these squares are painted black, while the rest are white. Jimin wants to cut the board into 8×8-sized chessboards. A chessboard must have alternating black and white squares. Specifically, each cell should be painted either black or white, and two squares sharing an edge must have different colors. Therefore, there are only two ways to color the chessboard. One has the top-left square white, and the other has it black. There is no guarantee that the board is already colored like a chessboard, so Jimin plans to cut it into 8×8 pieces and repaint some of the squares. Naturally, he can choose the 8×8 sections from anywhere. Your task is to write a program that calculates the minimum number of squares that Jimin needs to repaint. Input The first line contains two integers, N and M. N and M are natural numbers greater than or equal to 8 and less tha...
Read more

Binary Search: The Efficient Solution for Sorted Arrays

Image
Binary Search is a powerful algorithm that allows you to efficiently search for a target element within a sorted array. This algorithm works by repeatedly dividing the search space in half, which makes it an extremely efficient method for finding elements in large, ordered datasets. The Prerequisite: Sorted Array Before we dive into the details of Binary Search, it's important to understand that this algorithm can only be applied to sorted arrays. If the array is not sorted, Binary Search will not work correctly, and you may end up with incorrect results. The reason for this requirement is that Binary Search relies on the fact that the array is already in order. This allows the algorithm to make informed decisions about which half of the array to search next, based on the comparison between the target element and the middle element of the current search space. The Binary Search Algorithm The Binary Search algorithm follows these steps: 1. Initialize the search space: Set the lowe...
Read more

[BaekJun,C++]1929: finding primes

Image
  https://www.acmicpc.net/problem/1929 Problem: Write a program that prints all prime numbers between M and N, inclusive. Input: The natural numbers M and N are given on the first line, separated by a space. (1 ≤ M ≤ N ≤ 1,000,000) The input guarantees that there is at least one prime number between M and N. Output: Print the prime numbers in ascending order, one per line. #include < iostream > #include < cstdio > #include < algorithm > using namespace std; int m, n; int main(void) { cin >> m >> n; int size = n - m + 1; int* prime = new int[n + 1]; prime[1] = 0; for (int i = 2; i < n + 1; i++) { prime[i] = 1; } //eratostheneses sieve for (int i = 2; i < n + 1;i++) { if (prime[i] == 0) { continue;// continue, break } else { for (int j = i * 2; j < n + 1; j += i) { //you don't always have to incerase the index by 1 prime[j] = 0; } } ...
Read more