[Python] Binary Search Issue: Fixing Failing Test Cases with Rotated Array and Duplicates...

def binary_search(lo, hi, condition):

while lo <= hi:

mid = (lo + hi) // 2

result = condition(mid)

if result == 'found':

return mid

elif result == 'left':

hi = mid - 1

else:

lo = mid + 1

return -1


def count_rotations_generic(nums):

if not nums:

return -1



def condition(mid):



if mid > 0 and nums[mid] < nums[mid - 1]:

return 'found'



elif nums[mid] < nums[len(nums)-1]:

return 'left'



elif nums[mid] == nums[len(nums)-1]:

return 'left'



else:

return 'right'



return binary_search(0, len(nums)-1, condition)


TEST CASES:

TEST CASE #0

Input: {'nums': [19, 25, 29, 3, 5, 6, 7, 9, 11, 14]}

Expected Output: 3

Actual Output: 3

Execution Time: 0.014 ms

Test Result: PASSED

TEST CASE #1

Input: {'nums': [13, 14, 17, 18, 19, 6, 8, 11]}

Expected Output: 5

Actual Output: 5

Execution Time: 0.009 ms

Test Result: PASSED

TEST CASE #2

Input: {'nums': [0, 1, 2, 3, 4, 5]}

Expected Output: -1

Actual Output: -1

Execution Time: 0.009 ms

Test Result: PASSED

TEST CASE #3

Input: {'nums': [9, 2, 3, 4, 5, 6, 7, 8]}

Expected Output: 1

Actual Output: 1

Execution Time: 0.008 ms

Test Result: PASSED

TEST CASE #4

Input: {'nums': [9, 2, 3, 4, 5, 6, 7, 8]}

Expected Output: 1

Actual Output: 1

Execution Time: 0.005 ms

Test Result: PASSED

TEST CASE #5

Input: {'nums': [3, 4, 5, 6, 7, 8]}

Expected Output: -1

Actual Output: -1

Execution Time: 0.006 ms

Test Result: PASSED

TEST CASE #6

Input: {'nums': []}

Expected Output: -1

Actual Output: -1

Execution Time: 0.002 ms

Test Result: PASSED

TEST CASE #7

Input: {'nums': [5]}

Expected Output: -1

Actual Output: -1

Execution Time: 0.006 ms

Test Result: PASSED

TEST CASE #8

Input: {'nums': [6, 6, 7, 8, 9, 9, 9, 0, 1, 3, 3, 4, 5, 5]}

Expected Output: 7

Actual Output: 7

Execution Time: 0.009 ms

Test Result: PASSED

TEST CASE #9

Input: {'nums': [5, 5, 6, 7, 7, 8, 8, 1, 1, 4, 5, 5, 5]}

Expected Output: 7

Actual Output: 7

Execution Time: 0.006 ms

Test Result: PASSED

TEST CASE #10

Input: {'nums': [6, 6, 6, 6, 1, 6]}

Expected Output: 4

Actual Output: -1

Execution Time: 0.014 ms

Test Result: FAILED

TEST CASE #11

Input: {'nums': [5, 5, 5, 5, 5, 5, 5]}

Expected Output: -1

Actual Output: -1

Execution Time: 0.009 ms

Test Result: PASSED

TEST CASE #12

Input: {'nums': [5, 1, 5, 5, 5, 5, 5]}

Expected Output: 1

Actual Output: 1

Execution Time: 0.006 ms

Test Result: PASSED

TEST CASE #13

Input: {'nums': [5, 6, 1, 1, 1, 1, 1, 4]}

Expected Output: 2

Actual Output: 2

Execution Time: 0.007 ms

Test Result: PASSED

SUMMARY

TOTAL: 14, PASSED: 13, FAILED: 1

Its passing some text cases but failing case#10 or case#12.

The reason is the lo , mid , and hi are equal so the code is confused where to go left or right.

I want to make changes in condition function so it can deal with this issue.

Continue reading...