Thắc mắc về số lần so sánh trong thuật toán Binary Search

#1 
public static int BinarySearch(int[] a, int searchValue) {
    int low = 0;
    int high = a.length - 1;
      
    while (low < high) {
        int mid = (low + high) / 2;
        if (a[mid] == searchValue) {
            return mid;
        } else if (a[mid] < searchValue) {
            low = mid + 1;
        } else if (a[mid] > searchValue) {
            high = mid - 1;
        }

    }
    return -1;
}

Em có đọc trên mạng thì với mảng gồm n phần tử, sẽ cần log2(n) phép so sánh (operations) để tìm ra được số mình cần tìm

Nhưng ví dụ em có một mảng là các số 3 4 5 6

Muốn tìm ra số 6 rồi return lại vị trí số 6 trong mảng phải cần 3 lần so sánh chứ ạ

  1. 6 với 4
  2. 6 với 5
  3. 6 với chính 6 để return lại vị trí
#2

Không phải, mà là O(log2(n)), tức là một số k lần log2(n), bài này là từ 1 đến 2 lần (vì đúng ra so = với < rồi thì > là else).

1 Like
#3

Trong sách nó ghi cần log2(n) operations mà anh

#4

Viết bằng kí pháp big-O thì đúng thật, còn viết không là trật lất :smiley: phải đếm nữa.

1 Like
#5

Số lần Operations là log2(n) mà bác

#6

Vậy nếu searchValue == a[n-1] thì có phải là 3log2(n) ops không :smiley: phải có big-O thì mới đúng.

Thường T(n) = O(logn) tức là T(n) = c*logn.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?