Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Java - Tìm kiếm một phần tử sử dụng trong mảng sử dụng thuật tìm kiếm nhị phân.
Viết chương trình thực hiện các công việc sau:
- Nhập liệu cho mảng có n phần tử nguyên (n > 0) từ bàn phím.
- Nhập số nguyên k từ bàn phím.
- Tìm kiếm phần tử đầu tiên trong mảng có giá trị bằng k và thông báo lên màn hình vị trí của phần tử đó. Nếu không có phần tử nào của mảng có giá trị bằng k thì thông báo "Trong mảng không có phần tử nào chứa giá trị cần tìm."
Yêu cầu kỹ thuật: Chương trình phải kiểm tra n nhập vào: nếu n <= 0 thì yêu cầu nhập lại số phần tử cho đến khi thỏa mãn điều kiện và phải sử dụng phương pháp tìm kiếm nhị phân.
Bài giải
-------------------- ######## --------------------
Hướng dẫn: Thuật toán tìm kiếm nhị phân được mô tả như sau: Trong trường hợp các phần tử trong mảng đã được sắp xếp (tăng dần hoặc giảm dần) thì chúng ta có thể dùng giải thuật tìm kiếm nhị phân để giảm số phép so sánh (tức làm giảm độ phức tạp tính toán). Các bước sử dụng thuật toán này được miêu tả như sau:
Bước 1: Thực hiện sắp xếp mảng (tăng dần hoặc giảm dần). Ở đây, tôi sắp xếp các phần tử theo thứ tự tăng dần.
Bước 2: Gọi d và c là phạm vi tìm kiếm (lúc đầu d = 0, c = n - 1, với n là số phần tử của mảng), l là vị trí của phần tử đứng giữa mảng (l = (d + c) / 2). Nếu phần tử tại vị trí l bằng với số nguyên k cần tìm thì kết luận tìm được k ở vị trí l trong mảng. Nếu phần tử tại vị trí l lớn hơn k thì lặp lại việc tìm kiếm k trong nửa đầu của mảng, nếu phần tử tại vị trí l nhỏ hơn k thì lặp lại việc tìm kiểm k trong nửa cuối của mảng.
public static void main(String[] args) {
int n, temp, max = 100, k, c, d, l;
Scanner scanner = new Scanner(System.in);
// khai báo và cấp phát bộ nhớ cho mảng A
int array[] = new int[max];
// nhập số phần tử của mảng
// kiểm tra nếu n <= 0 hoặc n > max - 1
// thì phải nhập lại
do {
System.out.println("Nhập số phần tử của mảng: ");
n = scanner.nextInt();
} while (n <= 0 || n > max-1);
System.out.println("Nhập giá trị cho các phần tử của mảng: ");
for (int i = 0; i < n; i++) {
System.out.print("array[" + i + "] = ");
array[i] = scanner.nextInt();
}
// sắp xếp tăng dần các phần tử bằng phương pháp Exchange sort
// vòng lặp for sẽ duyệt i và j
// i chạy từ 0 đến n - 1, j chay từ i + 1 đến n - 1
// nếu phần tử tại chỉ số j nhỏ hơn phần tử tại i
// thì sẽ hoán đổi vị trí 2 phần tử này cho nhau
for (int i = 0; i < n - 1; i++) {
for (int j = i+1; j <= n - 1; j++) {
if (array[j] < array[i]) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
// tìm kiếm phần tử trong mảng
System.out.println("Nhập số nguyên cần tìm: ");
k = scanner.nextInt();
d = 0;
c = n - 1;
// duyệt vòng lặp while
// nếu d còn nhỏ hơn hoặc bằng c thì còn tiếp tục thực hiện thân vòng lặp
while (d <= c) {
l = (d + c) / 2;
// nếu phần tử tại vị trí j bằng số nguyên k cần tìm
// thì thông báo tìm thấy số k tại vị trí j
// và kết thúc vòng lặp
if (array[l] == k) {
System.out.println("Tìm thấy phần tử " + k + " tại vị trí " + l);
return; // kết thúc vòng lặp while và bỏ qua các lệnh bên dưới
} else if (array[l] < k) {
// nếu phần tử tại l nhỏ hơn số nguyên k
// thì tăng d = l + 1
// và quay lại thực hiện vòng lặp while
d = l + 1;
} else {
// nếu phần tử tại l lớn hơn số nguyên k
// thì giảm c = l - 1
// và quay lại thực hiện vòng lặp while
c = l - 1;
}
}
// nếu sau khi thực hiện vòng lặp while
// mà không tìm thấy số cần tìm
// thì hiển thị thông báo không tìm thấy
System.out.println("Trong mảng không có phần tử nào chứa giá trị cần tìm.");
}
Kết quả sau khi biên dịch chương trình:
Bài viết này được đăng tại [free tuts .net]
Trong bài tập này, các bạn thấy tôi có sử dụng lệnh return (chi tiết về từ khóa này tôi sẽ nói ở các bài sau). Cả 2 lệnh return và break đều dùng để kết thúc vòng lặp. nhưng khác nhau ở chỗ: lệnh break là thoát khỏi vòng lặp và thực hiện các lệnh bên dưới, còn lệnh return là thoát khỏi vòng lặp và bỏ qua các lệnh bên dưới. Như trong đoạn chương trình trên, nếu tìm thấy số nguyên cần tìm thì chương trình sẽ hiển thị vị trí của số nguyên đó và kết thúc chương trình.
Câu hỏi thường gặp liên quan:
- Java - Nhập mảng và thực hiện các thao tác trên mảng.
- Java - Sắp xếp mảng tăng dần sử dụng phương pháp nổi bọt (Bubble sort).
- Java - Tìm kiếm một phần tử sử dụng trong mảng sử dụng thuật tìm kiếm nhị phân.
- Java - Kiểm tra mảng một chiều vừa nhập có phải là mảng đối xứng hay không?
- Java - Tìm và in ra màn hình số lượng số nguyên lẻ, số lượng số nguyên chẵn trong mảng.
- Java - Xóa phần tử có giá trị k trong mảng (k nhập từ bàn phím).
- Java - Nhập mảng và thực hiện tách các số chẵn và lẻ trong mảng sang hai mảng khác.
- Java - Tách một nửa đầu của mảng ban đầu sang mảng thứ nhất và nửa còn lại sang mảng thứ hai.
- Java - Viết chương trình hiển thị các phần tử chia hết cho 5 trong mảng.
- Java - Đếm số lần xuất hiện của 1 phần tử được nhập từ bàn phím.
- Java - Bài tập tổng hợp các thao tác trên mảng.
- Java - Viết chương trình nhập mảng sao cho không có phần tử nào trùng nhau.
