Java Tìm kiếm giá trị trong mảng với thời gian nhỏ hơn O(n).

Đây là một câu hỏi khá hay mà tôi đọc được trên stackexchange, câu hỏi đặt ra vấn đề là làm cách nào để tìm kiếm một đối tượng trong mảng với tốc độ nhỏ hơn O(n), có rất nhiều câu trả lời khác nhau, tuy chưa tính là hoàn hảo nhưng từ đây ta học và hiểu được rất nhiều vấn đề về tốc độ của chương trình.

"I have an array where each element is either one less or one greater than the preceding element {xi=xi−1±1}. I wish to find an element in it in less than O(n) time."

Đề bài đưa ra là tôi có một mảng Array ở đó mỗi phần tử ở gần nhau sẽ nhỏ hơn hoặc lớn phần tử kế bên 1 đơn vị, mô tả theo công thức sẽ là {xi=xi−1±1}, tôi muốn tìm một giải pháp nào đó để tìm một phần tử trong mảng với thời gian nhỏ hơn O(n).

Sau khi xem qua tôi tổng hợp lại 2 phương thức tìm kiếm, một của người đặt vấn đề và một của người trả lời vấn đề, tuy nhiên tôi cũng chưa hiểu hết được ý của người trả lời vấn đề, nhưng lỡi ngâm rồi bỏ thì uổng nên viết lại và rất mong được sự chia sẽ ý của các bạn về vần đề này, để có thể biết chi tiết hơn bạn có thể vào trang thảo luận xem trực tiếp http://codereview.stackexchange.com/questions/36547/searching-in-an-array-in-less-than-on-time.


Dưới đây là code tôi tổng hợp và viết lại:

/**
 *
 * @author bnson
 * @website vnlives.net
 */
public class SearchingArrayTimeComplexity {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here        
        long startTime = System.currentTimeMillis();        
       
        int[] arr = {     2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 3    };
       
        int index_01 = searchArray_01(arr, 4, 3);
        System.out.println("searchArray_01 Index finder: " + index_01);
       
        int index_02 = searchArray_02(arr, 4, 3);
        System.out.println("searchArray_02 Index finder: " + index_02);       
       
        long endTime = System.currentTimeMillis();
        System.out.println("It took " + (endTime - startTime) + " milliseconds");
       
    }
   
    public static int searchArray_01(int[] arr, int p, int elem) {

        if (p > arr.length - 1 || p < 0) {
            return -1;
        }

        if (arr[p] == elem) {
            return p;

        } else {
            int diff = Math.abs(elem - arr[p]);
            int index = searchArray_01(arr, p + diff, elem);
            if (index == -1) {
                index = searchArray_01(arr, p - diff, elem);
                if (index == -1) {
                    return -1;
                }
            }
            return index;
        }
    }
   
    public static int searchArray_02(int[] arr, int p, int elem) {

        for (int i = p; i < arr.length;) {
            if (arr[i] == elem) {
                return i;
            }
            i  += Math.abs(elem - arr[i]);
        }
        return -1;
    }
   
}

Dưới đây là kết quả:

searchArray_01 Index finder: 5
searchArray_02 Index finder: 5
It took 0 milliseconds

P/S: Rất mong nhận được phản hồi thảo luận của các bạn lập trình viên về vấn đề này.



Writer: +Bui Ngoc Son