Thuật toán logarit rời rạc

Question

Tôi thường thấy rằng logarit rời rạc là một vấn đề khó khăn. Tuy nhiên, tôi không hoàn toàn hiểu được điều này. Dường như với tôi rằng một tìm kiếm nhị phân thông thường sẽ làm tốt để phục vụ mục đích này. Ví dụ,

binary_search(base, left, right, target) { 
    if (pow(base, left) == target) 
     return left; 
    if (pow(base, right) == target) 
     return right; 
    if (pow(base, (left + right)/2) < target) 
     return binary_search(base, (left + right)/2, right, target); 
    else 
     return binary_search(base, left, (left + right)/2, target); 
} 

log(base, number) { 
    left = 1; 
    right = 2; 
    while(pow(base, p) < number) { 
     left = right; 
     right *= 2; 
    } 
    return binary_search(base, left, right, number); 
} 

Nếu việc thực hiện ngây thơ chỉ incrementing p cho đến khi pow(base, p) là O (n), thì chắc chắn tìm kiếm nhị phân này là O (log (n)^2).

Hoặc tôi không hiểu thuật toán này được đo như thế nào?

Chỉnh sửa: Tôi không thường viết tìm kiếm nhị phân, vì vậy nếu có lỗi triển khai tầm thường, vui lòng bỏ qua hoặc chỉnh sửa trong bản sửa lỗi.

Answer 1

Thuật toán của bạn giả định rằng < b ngụ ý pow (cơ sở, a) < pow (cơ sở, b).

Điều này đúng với số tự nhiên, nhưng nó sẽ không hoạt động trong một nhóm tuần hoàn hữu hạn (khi 'pow' được tính modulo một số số).