File under test: https://github.com/wangzheng0822/algo/tree/master/python/16_bsearch/bsearch_variants.py

Function under test: bsearch_left_not_less()

Function do: Binary search of the index of the first element not less than a given target in the ascending sorted array. If not found, return -1.

def bsearch_left_not_less(nums: List[int], target: int) -> int:
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    if low < len(nums) and nums[low] >= target:
        return low
    else:
        return -1

Untitled

Control-flow graph

12-Page-1.drawio.png

MCC Coverage testcase

Line 5

Path nums[mid] < target Test case Expected output Actual output Result
Start → 2 → 3 → 4 → 5 → 7-8 → 3 → 9 → 10 → End F num = [1, 2, 5]
target = 1 0 0 pass
Start → 2 → 3 → 4 → 5 → 6 → 3 → 9 → 10 → End T num = [1, 2, 5]
target = 5 2 2 pass

Line 9

Path low < len(nums) nums[low] ≥ target Test case Expected ouput Actual output Result
Start → 2 → 3 → 9 → 10 → End T T num = [1, 2, 3, 3, 5]
target = 2 1 1 pass
Start → 2 → 3 → 9 → 11-12 → End F T never happen
Start → 2 → 3 → 9 → 11-12 → End T F num = [1, 2, 3, 3, 5]
target = 6 -1 -1 pass
Start → 2 → 3 → 9 → 11-12 → End F F num = []
target = 1 -1 -1 pass

Data-flow graph

12-Page-2.drawio (1).png

All DU path coverage testcase

All du path for nums

Path Test case Expected output Actual output Result
1 → 2 nums = [1, 2, 5]
target = 2 1 1 pass
1 → 2 → 3 → 4 → 5 nums = [1, 2, 5]
target = 2 1 1 pass
1 → 2 → 3 → 9 nums = [1]
target = 1 0 0 pass
1 → 2 → 3 → 4 → 5 → 6 → 3 → 9 nums = [1, 2, 5]
target = 1 0 0 pass
1 → 2 → 3 → 4 → 5 → 7-8 → 3 → 9 nums = [1, 3, 5]
target = 5 2 2 pass

All DU path for target

Path Test case Expected output Actual output Result
1 → 2 → 3 → 4 → 5 nums = [1, 2, 5]
target = 2 1 1 pass
1 → 2 → 3 → 9 nums = [1, 2, 5]
target = 2 1 1 pass
1 → 2 → 3 → 4 → 5 → 6 → 3 → 9 nums = [1, 2, 5]
target = 1 0 0 pass
1 → 2 → 3 → 4 → 5 → 7-8 → 3 → 9 nums = [1, 2, 5]
target = 5 2 2 pass