Cách triển khai tìm kiếm nhị phân bằng phương pháp lặp lại
Một trong những thuật toán cơ bản nhất trong khoa học máy tính là thuật toán Tìm kiếm nhị phân. Bạn có thể triển khai Tìm kiếm nhị phân bằng hai phương pháp: phương pháp lặp và phương thức đệ quy. Trong khi cả hai phương pháp đều có cùng độ phức tạp về thời gian, phương pháp lặp lại hiệu quả hơn nhiều về độ phức tạp về không gian.
Phương thức lặp có độ phức tạp về không gian là O (1) so với O (logn) được sản xuất bằng phương pháp đệ quy. Vì vậy, làm thế nào bạn có thể triển khai thuật toán Tìm kiếm nhị phân bằng cách sử dụng phương pháp lặp trong C, C ++ và Python?
Mục Lục
Tìm kiếm nhị phân là gì?
Tìm kiếm nhị phân còn được gọi là tìm kiếm nửa khoảng, tìm kiếm logarit, hoặc tìm kiếm nhị phân là một thuật toán tìm kiếm và trả về vị trí của một phần tử trong một mảng được sắp xếp. Phần tử tìm kiếm được so sánh với phần tử ở giữa. Lấy giá trị trung bình của giới hạn dưới và giới hạn trên, bạn có thể tìm thấy các yếu tố ở giữa.
Nếu phần tử tìm kiếm lớn hơn phần tử ở giữa, điều đó có nghĩa là tất cả các phần tử ở phía bên trái đều nhỏ hơn phần tử tìm kiếm. Vì vậy, điều khiển dịch chuyển sang phía bên phải của mảng (nếu mảng theo thứ tự tăng dần) bằng cách tăng giới hạn dưới đến vị trí tiếp theo của phần tử ở giữa.
Tương tự, nếu phần tử tìm kiếm nhỏ hơn phần tử ở giữa, điều đó có nghĩa là tất cả các phần tử ở phía bên phải đều lớn hơn phần tử tìm kiếm. Vì vậy, điều khiển chuyển sang phần bên trái của mảng bằng cách thay đổi giới hạn trên thành vị trí trước đó của phần tử ở giữa.
Điều này làm giảm đáng kể số lượng so sánh so với việc triển khai tìm kiếm tuyến tính trong đó số lượng so sánh bằng với số phần tử trong trường hợp xấu nhất. Phương pháp này tỏ ra rất hữu ích để tìm số trong danh bạ hoặc các từ trong từ điển.
Dưới đây là biểu diễn theo sơ đồ của thuật toán Tìm kiếm nhị phân:
Tìm kiếm nhị phân bằng C
Làm theo các bước sau để triển khai Tìm kiếm nhị phân bằng C:
Toàn bộ mã nguồn của Chương trình tìm kiếm nhị phân sử dụng C, C ++, Java và Python có trong kho lưu trữ GitHub này.
Chương trình định nghĩa một hàm, Tìm kiếm nhị phân()trả về chỉ mục của giá trị được tìm thấy hoặc -1 nếu nó không có mặt:
#include <stdio.h>int binarySearch(int arr[], int arr_size, int search_number) {
}
Chức năng hoạt động bằng cách thu hẹp không gian tìm kiếm lặp đi lặp lại. Vì tìm kiếm nhị phân hoạt động trên các mảng được sắp xếp, bạn có thể tính giá trị giữa, nếu không thì không có ý nghĩa. Bạn có thể yêu cầu người dùng cung cấp một mảng được sắp xếp hoặc sử dụng các thuật toán sắp xếp như Bubble hoặc Selection sort.
Các Thấp và cao các biến lưu trữ các chỉ mục đại diện cho các ranh giới của không gian tìm kiếm hiện tại. giữa lưu trữ chỉ mục ở giữa:
int low = 0, high = arr_size - 1, mid;Chính trong khi() vòng lặp sẽ thu hẹp không gian tìm kiếm. Nếu giá trị của chỉ mục thấp hơn bao giờ hết lớn hơn chỉ mục cao, thì không gian tìm kiếm đã hết, vì vậy giá trị không thể hiện diện.
while (low <= high) {
}return -1;
Sau khi cập nhật điểm giữa ở đầu vòng lặp, có ba kết quả có thể xảy ra:
- Nếu giá trị ở điểm giữa là giá trị mà chúng tôi đang tìm kiếm, hãy trả về chỉ mục đó.
- Nếu giá trị điểm giữa lớn hơn giá trị chúng tôi đang tìm kiếm, hãy giảm giá trị cao xuống.
- Nếu giá trị điểm giữa nhỏ hơn, hãy tăng giá trị thấp hơn.
mid = (low + (high - low)) / 2;if (arr[mid] == search_number)
return mid;
else if (arr[mid] > search_number)
high = mid - 1;
else
low = mid + 1;
Kiểm tra chức năng với đầu vào của người dùng. Sử dụng scanf () để nhận đầu vào từ dòng lệnh, bao gồm kích thước mảng, nội dung của nó và một số để tìm kiếm:
int main() {
int arr[100], i, arr_size, search_number;
printf("Enter number of elements: ");
scanf("%d", &arr_size);
printf("Please enter numbers: ");for (i = 0; i < arr_size; i++) {
scanf("%d", &arr[i]);
}
printf("Enter number to be searched: ");
scanf("%d", &search_number);
i = binarySearch(arr, arr_size, search_number);
if (i==-1)
printf("Number not present");
else
printf("Number is present at position %d", i + 1);
return 0;
}
Nếu bạn tìm thấy số, hãy hiển thị vị trí hoặc chỉ số của nó, nếu không sẽ có thông báo cho biết số đó không có.
Tìm kiếm nhị phân bằng C ++
Bạn có thể chuyển đổi chương trình C sang chương trình C ++ bằng cách nhập Dòng đầu ra đầu vào và sử dụng không gian tên std để tránh lặp lại nhiều lần trong suốt chương trình.
#include <iostream>
using namespace std;Sử dụng cout với nhà điều hành khai thác << thay vì printf () và cin với toán tử chèn >> thay vì scanf () và chương trình C ++ của bạn đã sẵn sàng.
printf("Enter number of elements: ");
cout << "Enter number of elements: ";
scanf("%d", &arr_size);
cin >> arr_size;Tìm kiếm nhị phân bằng Python
Vì Python không có hỗ trợ sẵn có cho mảng, hãy sử dụng danh sách. Xác định một chức năng, Tìm kiếm nhị phân()chấp nhận ba tham số, danh sách, kích thước của nó và một số để tìm kiếm:
def binarySearch(arr, arr_size, search_number):
low = 0
high = arr_size - 1
while low <= high:
mid = low + (high-low)
if arr[mid] == search_number:
return mid
elif arr[mid] > search_number:
high = mid - 1
else:
low = mid + 1
return -1Khởi tạo hai biến, Thấp và cao, để phục vụ như giới hạn dưới và giới hạn trên của danh sách. Tương tự như việc triển khai C, hãy sử dụng trong khi vòng lặp thu hẹp không gian tìm kiếm. Khởi tạo giữa để lưu trữ giá trị giữa của danh sách. Python cung cấp toán tử phân chia tầng (//) cung cấp số nguyên lớn nhất có thể.
Thực hiện so sánh và thu hẹp không gian tìm kiếm cho đến khi giá trị giữa bằng số tìm kiếm. Nếu số tìm kiếm không có, điều khiển sẽ trả về -1.
arr_size = int(input("Enter number of elements: "))
arr=[]
print("Please enter numbers: ", end=" ")
for i in range(0,arr_size):
arr.append(int(input()))
search_number = int(input("Enter number to be searched: "))
result = binarySearch(arr, arr_size, search_number)
if result == -1:
print("Number not present")
else:
print("Number is present at position ", (result + 1))Kiểm tra chức năng với đầu vào của người dùng. Sử dụng đầu vào() để có được kích thước danh sách, nội dung của nó và một số để tìm kiếm. Sử dụng int () để đánh máy đầu vào chuỗi được Python chấp nhận làm mặc định thành một số nguyên. Để thêm số vào danh sách, hãy sử dụng chắp thêm () hàm số.
Cuộc gọi Tìm kiếm nhị phân() và chuyển các đối số. Nếu bạn tìm thấy số, hãy hiển thị vị trí hoặc chỉ số của nó, nếu không sẽ có thông báo cho biết số đó không có.
Đầu ra của thuật toán tìm kiếm nhị phân
Sau đây là kết quả của thuật toán Tìm kiếm nhị phân khi phần tử có trong mảng:
Sau đây là kết quả của thuật toán Tìm kiếm nhị phân khi phần tử không có trong mảng:
Tìm hiểu các cấu trúc và thuật toán dữ liệu cơ bản
Tìm kiếm là một trong những thuật toán đầu tiên bạn học và thường được hỏi trong các cuộc thi viết mã, vị trí và phỏng vấn. Một số thuật toán khác bạn nên học là sắp xếp, băm, lập trình động, đối sánh chuỗi và thuật toán kiểm tra tính nguyên thủy.
Ngoài ra, điều cần thiết là phải hiểu độ phức tạp về thời gian và không gian của các thuật toán. Chúng là một trong những khái niệm quan trọng nhất trong Khoa học Máy tính trong việc xác định hiệu quả của bất kỳ thuật toán nào. Với kiến thức về Cấu trúc dữ liệu và Thuật toán, bạn nhất định phải xây dựng các chương trình tốt nhất.