fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Tìm kiếm tuần tự / tìm kiếm tuyến tính (Linear Search)
  5. // Tìm kiếm nhị phân (Binary Search)
  6. /*
  7. Ví dụ bài toán
  8. - Nhập vào dãy a có n chữ số tự nhiên, tìm xem x có trong dãy a hay không
  9. */
  10.  
  11. int n, x;
  12. int a[1000];
  13.  
  14. void LinearSearch(int a[], int n, int x) // Tìm kiếm tuyến tính
  15. {
  16.     for(int i = 0 ; i < n ; i ++)
  17.         if(a[i] == x) 
  18.         {
  19.             cout << "yes";
  20.             return ; // quay lại lên trên (bỏ toàn bộ code dưới nó nếu nó thực thi và kết thúc chương trình)
  21.         }
  22.     cout << "no";
  23. } // độ phức tạp thời gian: O(n) --> tức bỏ vào 1 tỷ phần tử thì chạy 1 tỷ lần (không tệ 8/10)
  24.  
  25. void BinarySearch(int a[], int n, int x) // Tìm kiếm nhị phân O(log2n)
  26. {
  27.     int l = 0, r = n - 1;
  28.     while(l <= r)
  29.     {
  30.         int mid = (l + r) / 2;
  31.         if(a[mid] < x)l = mid + 1;
  32.         else if(a[mid] > x)r = mid - 1;
  33.         else if(a[mid] == x)
  34.         {
  35.             cout << "yes";
  36.             return ;
  37.         }
  38.     }
  39.     cout << "no";
  40. } // Độ phức tạp thời gian: O(log2n)
  41.  
  42.  
  43. int main()
  44. {
  45.     cin >> n >> x;
  46.     for(int i = 0 ; i < n ; i ++)cin >> a[i];
  47.     LinearSearch(a, n, x);
  48.     cout << endl;
  49.     BinarySearch(a, n, x);
  50. }
  51.  
  52. /*
  53. Lưu ý: Trong bài toán tìm kiếm nhị phân, đầu vào phải là một dãy tăng dần
  54. mid = (l + r) / 2
  55.  
  56. Tức là vị trí của mid bị ảnh hưởng bởi 2 biến số l và r
  57. l = 0, r = 10;
  58. mid = (0 + 10) / 2
  59. mid = 5
  60.  
  61. --> dịch qua phải: thay đổi giá trị l (cận trái): l = mid + 1;
  62. --> dịch qua trái: thay đổi giá trị r (cận phải): r = mid - 1;
  63.  
  64. - l = 0, r = 4 (mid - 1)
  65. - mid = (l + r) / 2 = 2
  66.  
  67. - l = 3, r = 4
  68. - mid = (l + r) / 2 = 3
  69.  
  70. */
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
no
no
https://ideone.com/bicUFm
language:
C++14 (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!