Module: Tìm kiếm nhị phân


Problem

1/5

Tìm kiếm nhị phân trong mảng có thứ tự: bắt đầu (C++)

Theory Click to read/hide

Tìm kiếm nhị phân là một — hiệu quả; ước tính độ phức tạp của nó là O(log2(n)), trong khi tìm kiếm tuần tự thông thường có O(n). Điều này có nghĩa là, ví dụ, đối với một mảng gồm 1024 phần tử, tìm kiếm tuyến tính, trong trường hợp xấu nhất, khi phần tử mong muốn không có trong mảng, sẽ xử lý tất cả 1024 phần tử. Tìm kiếm nhị phân là đủ để xử lý các phần tử \(log_2(1024) = 10\). Kết quả này đạt được là do sau bước đầu tiên của vòng lặp, khu vực tìm kiếm thu hẹp xuống còn 512 phần tử, sau bước thứ hai – lên đến 256, v.v.

Nhược điểm của thuật toán này là yêu cầu sắp xếp dữ liệu, cũng như khả năng truy cập bất kỳ phần tử dữ liệu nào trong một khoảng thời gian không đổi (không phụ thuộc vào lượng dữ liệu). Do đó, thuật toán không thể hoạt động trên các mảng không có thứ tự và bất kỳ cấu trúc dữ liệu nào dựa trên danh sách được liên kết.


Thực hiện
tạm biệt (phải – trái > 1)  // Miễn là đường viền bên phải ở bên phải bên trái
nc
  giữa = (trái + phải) /< /span> 2; // Giữa khu vực tìm kiếm
  nếu (A[middle] >= b) thì
    phải = giữa; // Di chuyển đường viền bên phải
  nếu không
    trái = giữa; // Nếu không thì di chuyển đường viền bên trái
cc
nếu (A[right] == X) thì
  đầu ra bên phải;
nếu không thì
  đầu ra -1;

ở đâu:
A - mảng nguồn,
N - kích thước mảng,
X - số mong muốn.
 

Problem

Triển khai thuật toán tìm kiếm nhị phân.
 
Nhập dữ liệu 
Dòng đầu tiên chứa các số tự nhiên N và K (\(0<N <= 100000,\ 0< K< ;=10^9\) ). Dòng thứ hai chứa các phần tử N của mảng, được sắp xếp theo thứ tự tăng dần. Các phần tử của mảng là các số nguyên, mỗi số không vượt quá 109.
 
Đầu ra
Cần  K xuất số của nó trong mảng trên một dòng riêng biệt, nếu số này xuất hiện trong mảng và "KHÔNG" mặt khác.
 
Ví dụ
<đầu>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Đầu vào Đầu ra
1
105
1 2 3 4 5 6 7 8 9 10 
 5
Write the program below 
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int Search_Binary (vector<int> arr, int key)
{
	int  midd = 0, left =-1, right = arr.size();

                   
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, w, h, l, r, k, index;

	cin >> n >> k;

	vector<int> A(n);

	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

       index = Search_Binary (A, k);
 
	if (index >= 0) 
		cout << index+1;
	else
		cout << "NO";
}

     

Program check result

To check the solution of the problem, you need to register or log in!