TỔNG QUAN
CẤU TRÚC ĐIỀU KHIỂN
VÒNG LẶP
CHUỖI VÀ MẢNG
COLLECTIONS
THƯ VIỆN QUAN TRỌNG
HƯỚNG ĐỐI TƯỢNG
XỬ LÝ LUỒNG
EXCEPTION
LÀM VIỆC VỚI FILE
THAM KHẢO
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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.

Bài giải
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:

ketqua baitap3mang1chieu PNG

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 returnbreak đề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:

Cùng chuyên mục:

Khi nào dùng Default Methods trong Java 8

Khi nào dùng Default Methods trong Java 8

Ở 2 bài trước chúng ta đã tìm hiểu 2 tính năng mới của Java…

Cách chuyển chữ hoa thành chữ thường trong Java

Cách chuyển chữ hoa thành chữ thường trong Java

Trong bài viết này chúng ta sẽ tìm hiểu về cách chuyển đổi chữ in…

Bài tập tính tổng các số tự nhiên trong Java

Bài tập tính tổng các số tự nhiên trong Java

Các số dương 1, 2, 3, 4, ... được gọi là các số tự nhiên,…

Cách chuyển chữ thường thành chữ hoa trong Java

Cách chuyển chữ thường thành chữ hoa trong Java

Trong chuỗi có thể vừa có ký tự thường vừa có ký tự hoa, nhưng…

Cách viết hoa ký tự đầu tiên trong Java

Cách viết hoa ký tự đầu tiên trong Java

Để hiểu được bài này, các bạn cần có kiến thức căn bản về Java…

Hướng dẫn chuyển đổi giờ phút giây trong Java

Hướng dẫn chuyển đổi giờ phút giây trong Java

Để hiểu được chương trình, các bạn cần có kiến thức cơ bản về Java.…

Cách lấy thời gian hiện tại trong Java

Cách lấy thời gian hiện tại trong Java

Để hiểu được bài viết này, các bạn cần có kiến thức cơ bản sau…

Cách làm tròn số trong Java

Cách làm tròn số trong Java

Khi thực hiện tính toán, việc kết quả ra một con số thập phân dài…

Cách tìm ma trận chuyển vị trong Java

Cách tìm ma trận chuyển vị trong Java

Quá trình hoán đổi giữa hàng và cột được gọi là chuyển vị của ma…

Cách chuyển ArrayList thành mảng và ngược lại trong Java

Cách chuyển ArrayList thành mảng và ngược lại trong Java

Để hiểu được bài này, các bạn cần có kiến thức cơ bản về mảng…

Cách nối hai mảng trong Java

Cách nối hai mảng trong Java

Mình sẽ thực hiện hai chương trình nối mảng. Chương trình thứ nhất nối hai…

Cách xóa khoảng trắng của chuỗi trong Java

Cách xóa khoảng trắng của chuỗi trong Java

Mình sẽ thực hiện hai chương trình khác nhau để các bạn có thể hiểu…

In ra tam giác bằng ký tự * và số trong Java

In ra tam giác bằng ký tự * và số trong Java

Mình sẽ giới thiệu cách để in ra các tam giác bằng ký tự *…

Tìm số lớn nhất trong mảng Java

Tìm số lớn nhất trong mảng Java

Các bạn cần tìm hiểu về mảng, cách khởi tạo và in mảng trong Java…

Tìm ước của một số nguyên trong Java

Tìm ước của một số nguyên trong Java

Trong bài viết này chúng ta sẽ tìm hiểu cách tìm tất cả các ước…

Cách kiểm tra số hoàn hảo trong Java

Cách kiểm tra số hoàn hảo trong Java

Cách kiểm tra số đối xứng trong Java

Cách kiểm tra số đối xứng trong Java

Trong bài viết này chúng ta sẽ kiểm tra một số có phải là số…

Đảo ngược một số trong Java

Đảo ngược một số trong Java

Mình sẽ giới thiệu các bạn cách đảo ngược một số sử dụng vòng lặp…

Tìm bội chung nhỏ nhất trong Java

Tìm bội chung nhỏ nhất trong Java

Mình sẽ sử dụng hai cách khác nhau để tìm BCNN. Cách thứ nhất mình…

Cách hoán đổi hai số trong Java

Cách hoán đổi hai số trong Java

Trong phần này mình sẽ sử dụng một biến tạm temp() làm biến trung gian…

Top