Module: Tìm kiếm tuyến tính và nhị phân cho các phần tử trong một mảng


Problem

6/7

Tìm kiếm nhị phân

Theory Click to read/hide

Tìm kiếm nhị phân
Tìm kiếm nhị phân (hoặc nhị phân) là thuật toán tìm kiếm hiệu quả và nhanh hơn tìm kiếm tuyến tính. 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ử, nhưng nó đủ để xử lý 10 phần tử bằng tìm kiếm nhị phân. 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 như vậy là yêu cầu sắp xếp thứ tự 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 mảng không có thứ tự.
 
Thuật toán
  1. Chọn phần tử ở giữa A[c] và so sánh với X.
  2. Nếu X = A[c] thì tìm thấy (dừng).
  3. Nếu X < A[c], tìm kiếm thêm trong nửa đầu.
  4. Nếu X > A[c], hãy xem thêm nửa sau.
     
Triển khai
L = 0; R=N; // đoạn đầu trong khi ( L < R - 1) { c = (L + R)/2; // tìm thấy giữa if ( X < A[c] ) // nén đoạn R=c; khác L = c; } nếu ( A[L] == X) cout << "A" << Đ<< "]=" << x; khác cout << "Không tìm thấy";

ở đâu:
A - mảng nguồn,
N - kích thước mảng,
X - số đã tìm kiếm,

Có thể triển khai các cách khác.
Ví dụ: sử dụng lối thoát sớm khỏi vòng lặp L = 0; R = N - 1; trong khi (R >= L) { c = (L + R)/2; nếu ( X == A[c] ) { nX = c; phá vỡ; } if (X < A[c]) R = giữa - 1; if (X > A[c]) L = giữa + 1; } nếu ( nX < 0) cout << "Không tìm thấy"; khác cout << "A" << nX<< "]=" << X;

Problem

Trong mảng đã cho, được sắp xếp theo thứ tự tăng dần, bạn cần tìm giá trị của phần tử bằng với giá trị X bằng tìm kiếm nhị phân. X được nhập từ bàn phím. Sửa đổi chương trình để nó giải quyết vấn đề Việc đánh số các phần tử bắt đầu từ số không. Nếu không có phần tử nào như vậy, chương trình sẽ xuất ra Không tìm thấy.

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

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<iostream> 
using namespace std; 
main() 
{	
  const int Nmax=1000; 	
  int A[Nmax], i, L, R, X, N, c;	 
  cin >> N; 
  for (i=0; i<N; i++) 
    cin >> A[i]; 
  cin >> X; 
  L = 0; R = N;       
  while ( L < R-1 )     
       cout << "A["<< L << "]=" << X; 
  else cout << "Not found"; 
}

     

Program check result

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