Báo cáo test whitebox cho function Binary Search

---

Họ và tên: Đỗ Xuân Anh

MSSV: 16020192

Lớp: K61-CA-CLC1

Code Binary Search

---

Link repo github: Binary Search

    private <T extends Comparable<T>> int BinarySearch(T array[], T key, int left, int right)
    {
        if (right < left)                                           //1
            return -1;                                              //2
        int median = (left + right) >>> 1;                          //3
        int comp = key.compareTo(array[median]);                    //4
        if (comp < 0) {                                             //5
            return BinarySearch(array, key, left, median - 1);      //6
        }                                                           //7
        if (comp > 0) {                                             //8
            return BinarySearch(array, key, median + 1, right);     //9
        }                                                           //10
        return median;                                              //11
    }

Bước 1: Đồ thị đường đi

---

Bước 2: Liệt kê các đường đi

---

Đường đi số 1: 1 → 2

Đường đi số 2: 1 → 3 → 4 → 5 → 6

Đường đi số 3: 1 → 3 → 4 → 5 → 8 → 9

Đường đi số 4: 1 → 3 → 4 → 5 → 8 → 11

Bước 3: Lập phương trình đường đi

---

Cho dãy: x1, x2, ..., xn; (x[i] <= x[i+1])
Key = c;

Đường đi số 1:

1. True → 1 <=> right < left
2. return -1 (Not found)

Đường đi số 2:

1. False → 1 <=> right > left
2. True → 5 <=> key < array[median]
3. return BinarySearch(array, key, left, median-1)

Đường đi số 3:

1. False → 1 <=> right > left
2. False → 5 <=> key >= array[median]
3. True → 8 <=> key > array[median]
4. return BinarySearch(array, key, median+1, right)

Đường đi số 4:

1. False → 1 <=> right > left
2. False → 5 <=> key >= array[median]
3. False → 8 <=> key = array[median]
4. return median (Founded)

Bước 4: Giải phương trình đường đi

---

Đường đi số 1:

Cho dãy: 2, 3, 4, 6, 7, 8, 9;
Key = 5;

1. left=0, right=6 → median=3
2. array[median]=6 > key=5
3. left=0, right=2 → median=1
4. array[median]=3 < key=5
5. left=2, right=2 → median=2
6. array[median]=4 < key=5
7. right=2 < left=3 → return -1 (Not found)

Đường đi số 2, 3 và 4:

Cho dãy: 2, 3, 4, 5, 6, 7, 8, 9;
Key = 5;

1. left=0, right=7 → median=4
2. array[median]=6 > key=5
3. left=0, right=3 → median=2
4. array[median]=4 < key=5
5. left=3, right=3 → median=3
6. array[median]=5 = key=5 → return 3 (Founded)