ngogoodbye
New member
## 704. Tìm kiếm nhị phân trong C ++
Tìm kiếm nhị phân là một thuật toán tìm kiếm tìm thấy vị trí của giá trị đích trong một mảng được sắp xếp.Nó hoạt động bằng cách liên tục chia mảng làm đôi cho đến khi tìm thấy giá trị mục tiêu.
### Thuật toán
Thuật toán tìm kiếm nhị phân hoạt động như sau:
1. Mảng được sắp xếp đầu tiên theo thứ tự tăng dần.
2. Giá trị đích được so sánh với phần tử giữa của mảng.
3. Nếu giá trị đích bằng với phần tử giữa, thì vị trí của giá trị đích được trả về.
4. Nếu giá trị đích nhỏ hơn phần tử giữa, thì tìm kiếm được thực hiện ở nửa bên trái của mảng.
5. Nếu giá trị đích lớn hơn phần tử giữa, thì tìm kiếm được thực hiện ở nửa bên phải của mảng.
6. Các bước 3-5 được lặp lại cho đến khi tìm thấy giá trị đích hoặc mảng đã cạn kiệt.
### Độ phức tạp thời gian
Độ phức tạp về thời gian của tìm kiếm nhị phân là O (log n), trong đó n là số lượng các phần tử trong mảng.Điều này là do mảng được chia làm một nửa ở mỗi lần lặp, do đó số lần lặp cần thiết để tìm giá trị đích là logarit trong kích thước của mảng.
### Thực hiện
Sau đây là việc triển khai thuật toán tìm kiếm nhị phân trong C ++:
`` `C ++
#include <Istream>
#include <Vector>
sử dụng không gian tên STD;
// Hàm này thực hiện tìm kiếm nhị phân trên mảng đã cho và trả về chỉ mục của giá trị đích.
int nhị phân nghiên cứu (vector <int> mảng, int target) {
// Khởi tạo các con trỏ trái và phải.
int trái = 0;
int right = mảng.size () - 1;
// Trong khi con trỏ bên trái nhỏ hơn hoặc bằng con trỏ bên phải, tiếp tục tìm kiếm.
while (trái <= phải) {
// Tính phần tử giữa của mảng.
int mid = (trái + phải) / 2;
// Nếu giá trị đích bằng với phần tử giữa, thì hãy trả về chỉ mục của phần tử giữa.
if (mảng [mid] == target) {
trở lại giữa;
}
// Nếu giá trị đích nhỏ hơn phần tử giữa, thì hãy tìm kiếm nửa bên trái của mảng.
khác if (target <mảng [mid]) {
Phải = giữa - 1;
}
// Nếu giá trị đích lớn hơn phần tử giữa, thì tìm kiếm nửa bên phải của mảng.
khác {
trái = mid + 1;
}
}
// Nếu không tìm thấy giá trị đích, thì hãy trả về -1.
trả lại -1;
}
int main () {
// Tạo một vectơ số nguyên.
vector <int> mảng = {1, 3, 5, 7, 9};
// Nhận giá trị mục tiêu từ người dùng.
mục tiêu int;
cout << "Nhập giá trị đích:";
CIN >> mục tiêu;
// Thực hiện tìm kiếm nhị phân trên vectơ và in chỉ mục của giá trị đích.
int index = BinarySearch (ARR, Target);
cout << "Chỉ mục của giá trị đích là" << index << endl;
trả lại 0;
}
`` `
### Ví dụ
Sau đây là một ví dụ về cách thuật toán tìm kiếm nhị phân hoạt động trên một mảng số nguyên được sắp xếp:
`` `
[1, 3, 5, 7, 9]
Giá trị mục tiêu = 5
1. Mảng được sắp xếp đầu tiên theo thứ tự tăng dần.
2. Giá trị đích được so sánh với phần tử giữa của mảng, là 7.
3. Vì giá trị đích nhỏ hơn phần tử giữa, nên tìm kiếm được thực hiện ở nửa bên trái của mảng.
4. Nửa bên trái của mảng bây giờ là [1, 3, 5].
5. Giá trị đích một lần nữa được so sánh với phần tử giữa của mảng, là 3.
6.
=======================================
## 704. Binary Search in C++
Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the array in half until the target value is found.
### Algorithm
The binary search algorithm works as follows:
1. The array is first sorted in ascending order.
2. The target value is compared to the middle element of the array.
3. If the target value is equal to the middle element, then the position of the target value is returned.
4. If the target value is less than the middle element, then the search is performed on the left half of the array.
5. If the target value is greater than the middle element, then the search is performed on the right half of the array.
6. Steps 3-5 are repeated until the target value is found or the array is exhausted.
### Time Complexity
The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because the array is divided in half at each iteration, so the number of iterations required to find the target value is logarithmic in the size of the array.
### Implementation
The following is an implementation of the binary search algorithm in C++:
```c++
#include <iostream>
#include <vector>
using namespace std;
// This function performs a binary search on the given array and returns the index of the target value.
int binarySearch(vector<int> arr, int target) {
// Initialize the left and right pointers.
int left = 0;
int right = arr.size() - 1;
// While the left pointer is less than or equal to the right pointer, continue searching.
while (left <= right) {
// Calculate the middle element of the array.
int mid = (left + right) / 2;
// If the target value is equal to the middle element, then return the index of the middle element.
if (arr[mid] == target) {
return mid;
}
// If the target value is less than the middle element, then search the left half of the array.
else if (target < arr[mid]) {
right = mid - 1;
}
// If the target value is greater than the middle element, then search the right half of the array.
else {
left = mid + 1;
}
}
// If the target value is not found, then return -1.
return -1;
}
int main() {
// Create a vector of integers.
vector<int> arr = {1, 3, 5, 7, 9};
// Get the target value from the user.
int target;
cout << "Enter the target value: ";
cin >> target;
// Perform a binary search on the vector and print the index of the target value.
int index = binarySearch(arr, target);
cout << "The index of the target value is " << index << endl;
return 0;
}
```
### Example
The following is an example of how the binary search algorithm works on a sorted array of integers:
```
[1, 3, 5, 7, 9]
Target value = 5
1. The array is first sorted in ascending order.
2. The target value is compared to the middle element of the array, which is 7.
3. Since the target value is less than the middle element, the search is performed on the left half of the array.
4. The left half of the array is now [1, 3, 5].
5. The target value is again compared to the middle element of the array, which is 3.
6.
Tìm kiếm nhị phân là một thuật toán tìm kiếm tìm thấy vị trí của giá trị đích trong một mảng được sắp xếp.Nó hoạt động bằng cách liên tục chia mảng làm đôi cho đến khi tìm thấy giá trị mục tiêu.
### Thuật toán
Thuật toán tìm kiếm nhị phân hoạt động như sau:
1. Mảng được sắp xếp đầu tiên theo thứ tự tăng dần.
2. Giá trị đích được so sánh với phần tử giữa của mảng.
3. Nếu giá trị đích bằng với phần tử giữa, thì vị trí của giá trị đích được trả về.
4. Nếu giá trị đích nhỏ hơn phần tử giữa, thì tìm kiếm được thực hiện ở nửa bên trái của mảng.
5. Nếu giá trị đích lớn hơn phần tử giữa, thì tìm kiếm được thực hiện ở nửa bên phải của mảng.
6. Các bước 3-5 được lặp lại cho đến khi tìm thấy giá trị đích hoặc mảng đã cạn kiệt.
### Độ phức tạp thời gian
Độ phức tạp về thời gian của tìm kiếm nhị phân là O (log n), trong đó n là số lượng các phần tử trong mảng.Điều này là do mảng được chia làm một nửa ở mỗi lần lặp, do đó số lần lặp cần thiết để tìm giá trị đích là logarit trong kích thước của mảng.
### Thực hiện
Sau đây là việc triển khai thuật toán tìm kiếm nhị phân trong C ++:
`` `C ++
#include <Istream>
#include <Vector>
sử dụng không gian tên STD;
// Hàm này thực hiện tìm kiếm nhị phân trên mảng đã cho và trả về chỉ mục của giá trị đích.
int nhị phân nghiên cứu (vector <int> mảng, int target) {
// Khởi tạo các con trỏ trái và phải.
int trái = 0;
int right = mảng.size () - 1;
// Trong khi con trỏ bên trái nhỏ hơn hoặc bằng con trỏ bên phải, tiếp tục tìm kiếm.
while (trái <= phải) {
// Tính phần tử giữa của mảng.
int mid = (trái + phải) / 2;
// Nếu giá trị đích bằng với phần tử giữa, thì hãy trả về chỉ mục của phần tử giữa.
if (mảng [mid] == target) {
trở lại giữa;
}
// Nếu giá trị đích nhỏ hơn phần tử giữa, thì hãy tìm kiếm nửa bên trái của mảng.
khác if (target <mảng [mid]) {
Phải = giữa - 1;
}
// Nếu giá trị đích lớn hơn phần tử giữa, thì tìm kiếm nửa bên phải của mảng.
khác {
trái = mid + 1;
}
}
// Nếu không tìm thấy giá trị đích, thì hãy trả về -1.
trả lại -1;
}
int main () {
// Tạo một vectơ số nguyên.
vector <int> mảng = {1, 3, 5, 7, 9};
// Nhận giá trị mục tiêu từ người dùng.
mục tiêu int;
cout << "Nhập giá trị đích:";
CIN >> mục tiêu;
// Thực hiện tìm kiếm nhị phân trên vectơ và in chỉ mục của giá trị đích.
int index = BinarySearch (ARR, Target);
cout << "Chỉ mục của giá trị đích là" << index << endl;
trả lại 0;
}
`` `
### Ví dụ
Sau đây là một ví dụ về cách thuật toán tìm kiếm nhị phân hoạt động trên một mảng số nguyên được sắp xếp:
`` `
[1, 3, 5, 7, 9]
Giá trị mục tiêu = 5
1. Mảng được sắp xếp đầu tiên theo thứ tự tăng dần.
2. Giá trị đích được so sánh với phần tử giữa của mảng, là 7.
3. Vì giá trị đích nhỏ hơn phần tử giữa, nên tìm kiếm được thực hiện ở nửa bên trái của mảng.
4. Nửa bên trái của mảng bây giờ là [1, 3, 5].
5. Giá trị đích một lần nữa được so sánh với phần tử giữa của mảng, là 3.
6.
=======================================
## 704. Binary Search in C++
Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the array in half until the target value is found.
### Algorithm
The binary search algorithm works as follows:
1. The array is first sorted in ascending order.
2. The target value is compared to the middle element of the array.
3. If the target value is equal to the middle element, then the position of the target value is returned.
4. If the target value is less than the middle element, then the search is performed on the left half of the array.
5. If the target value is greater than the middle element, then the search is performed on the right half of the array.
6. Steps 3-5 are repeated until the target value is found or the array is exhausted.
### Time Complexity
The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because the array is divided in half at each iteration, so the number of iterations required to find the target value is logarithmic in the size of the array.
### Implementation
The following is an implementation of the binary search algorithm in C++:
```c++
#include <iostream>
#include <vector>
using namespace std;
// This function performs a binary search on the given array and returns the index of the target value.
int binarySearch(vector<int> arr, int target) {
// Initialize the left and right pointers.
int left = 0;
int right = arr.size() - 1;
// While the left pointer is less than or equal to the right pointer, continue searching.
while (left <= right) {
// Calculate the middle element of the array.
int mid = (left + right) / 2;
// If the target value is equal to the middle element, then return the index of the middle element.
if (arr[mid] == target) {
return mid;
}
// If the target value is less than the middle element, then search the left half of the array.
else if (target < arr[mid]) {
right = mid - 1;
}
// If the target value is greater than the middle element, then search the right half of the array.
else {
left = mid + 1;
}
}
// If the target value is not found, then return -1.
return -1;
}
int main() {
// Create a vector of integers.
vector<int> arr = {1, 3, 5, 7, 9};
// Get the target value from the user.
int target;
cout << "Enter the target value: ";
cin >> target;
// Perform a binary search on the vector and print the index of the target value.
int index = binarySearch(arr, target);
cout << "The index of the target value is " << index << endl;
return 0;
}
```
### Example
The following is an example of how the binary search algorithm works on a sorted array of integers:
```
[1, 3, 5, 7, 9]
Target value = 5
1. The array is first sorted in ascending order.
2. The target value is compared to the middle element of the array, which is 7.
3. Since the target value is less than the middle element, the search is performed on the left half of the array.
4. The left half of the array is now [1, 3, 5].
5. The target value is again compared to the middle element of the array, which is 3.
6.
