01/10/2018, 15:57

Nhờ mọi người check code thuật toán tìm kiếm nhị phân

Chào mọi người, em là thành viên mới và mong sẽ học hỏi được nhiều từ mọi người ạ.
Dưới đây là em code tìm kiếm nhị phân bằng Java, mọi người thử check xem giúp em cách em làm như nào, và cho em tham khảo cách của mọi người được không ạ? Em xin cảm ơn nhiều ạ.

import java.io.IOException;
import java.util.*;

public class arraytest {
    public static void main (String args[]){
        Scanner inp = new Scanner(System.in);
        int n; // Số phần tử của mảng
        System.out.print("Nhập số phần tử của mảng: ");
        n = inp.nextInt();
        int a[] = new int[n]; // Khai báo mảng Int
        //Nhập mảng
        System.out.println("Nhập mảng tăng dần: ");
        for (int i = 0; i < n;i++){
            a[i] = inp.nextInt();
        }
        //Tìm kiếm nhị phân
        int m;
        System.out.print("Nhập số cần tìm: ");
        m = inp.nextInt();

        binarysearch(a,m,0,n);
        }

    public static void binarysearch(int[] a,int m,int f, int n){
        int o = (int)((n-f)/2 + f);
        if(m != a[o]) {

            if(n-f < 2){
                System.out.println("Không tìm thấy!");
            }
            else{
                if (m < a[o]) {
                    binarysearch(a, m, 0, o);
                }
                else if (m > a[o]) {
                    binarysearch(a, m, o, n);
                }
            }

        }
        else System.out.printf("Số cần tìm nằm ở vị trí %d",o);
    }
}
HK boy viết 18:13 ngày 01/10/2018
  • Bạn đặt tên biến o, n, f, m khó hiểu quá.

(n-f)/2

Kết quả này luôn là số nguyên, + f nguyên vẫn là số nguyên, không cần ép kiểu.

  • Bạn code quá dài dòng, với lại có thể khử đệ quy được.

Bạn tham khảo:

int binary_search(int[] a, int left, int right, int x) {
// return the index of element x in a[left..right]
	while (1) { // infinite loop
		if (left > right)
			return -1; // x not in a[left..right]
		else if (left == right) {
			return (a[left] == x ? left : -1); // I'm lazy
		} else {
			int mid = (left + right) / 2;
			if (a[mid] == x)
				return mid;
			else if (a[mid] > x)
				right = mid;
			else if (a[mid] < x) // you can remove this if condition
				left = mid;
		}
	}
}
Bài liên quan
0