含重复元素有序数组二分查找最小索引实现Bug排查

这是我首次在此发帖，若未遵循社区最佳实践还请见谅。我需要实现的算法针对可能存在重复元素的有序数组，满足以下两个要求：

• 若目标元素不存在于数组中，返回-1；
• 若目标元素存在，返回其出现位置的最小索引。

我已编写了适用于无重复元素数组的二分查找（binary search）算法，经黑盒测试验证，该无重复版本功能正常，可返回元素所在位置或-1。后续我通过另一个函数递归调用该二分查找逻辑，在[0, position-1]区间内搜索目标元素的首次出现位置。

目前我的代码未通过黑盒测试，触发答案错误（Wrong Answer，非超时错误）。我已测试了所有能想到的边界用例，还通过朴素搜索算法做了暴力对比测试，均未复现问题。我希望获得现有实现的错误排查方向指导，而非直接给出替代解决方案。

输入 #

5  #array size
3 4 7 7 8  #array elements need to be sorted
5         #search query array size
3 7 2 8 4  #query elements

输出 #

0 2 -1 4 1

class BinarySearch:
 
 def __init__(self,input_list,query):
        
    self.array=input_list
    self.length=len(input_list)
    self.query=query
    return
 
 def binary_search(self,low,high):
    '''
    Implementing the binary search algorithm with distinct numbers on a 
    sorted input.
    '''
    
    #trivial case
    if (self.query<self.array[low]) or (self.query>self.array[high-1]):
        
        return -1
        
    elif (low>=high-1) and self.array[low]!=self.query:
        
        return -1
    else:
        m=low+int(np.floor((high-low)/2))
        if self.array[low]==self.query:
            return low
        elif (self.array[m-1]>=self.query):
            return self.binary_search(low,m)
        elif self.array[high-1]==self.query:
            return high-1
        else:    
            return self.binary_search(m,high)
    return
        
class DuplicateBinarySearch(BinarySearch):
     
     def __init__(self,input_list,query):
       
        BinarySearch.__init__(self,input_list,query)
     
     def handle_duplicate(self,position):
        '''
        Function handles the duplicate number problem.
        Input: position where query is identified.
        Output: updated earlier position if it exists else return 
        original position.
        '''
        
        if position==-1:
            return -1
        elif position==0:
            return 0
        elif self.array[position-1]!=self.query:
            return position
        else:
            new_position=self.binary_search(0,position)
            if new_position==-1 or new_position>=position:
                return position
            else:
                return self.handle_duplicate(new_position)
     
     def naive_duplicate(self,position):
        
        old_position=position
        if position==-1:
            return -1
        else:
            while position>=0 and self.array[position]==self.query:
                position-=1
            if position==-1:
                return old_position
                
            else:
                return position+1
     

 if __name__ == '__main__':
    num_keys = int(input())
    input_keys = list(map(int, input().split()))
    assert len(input_keys) == num_keys
    

    num_queries = int(input())
    input_queries = list(map(int, input().split()))
    assert len(input_queries) == num_queries
   

    for q in input_queries:
        item=DuplicateBinarySearch(input_keys,q)
        #res=item.handle_duplicate(item.binary_search(0,item.length))
        #res=item.naive_duplicate(item.binary_search(0,item.length))
        #assert res_check==res
        print(item.handle_duplicate(item.binary_search(0,item.length)), end=' ')
        #print(item.naive_duplicate(item.binary_search(0,item.length)), end=' ')

• 运行naive_duplicate逻辑时触发超时错误：

Failed case #56/57: time limit exceeded (Time used: 10.00/5.00, memory used: 42201088/536870912.)

• 运行基于二分查找的重复元素处理逻辑时触发答案错误：

Failed case #24/57: Wrong answer
(Time used: 0.11/5.00, memory used: 42106880/536870912.)

我通过如下修改修复了代码问题，但无法构造出触发原有代码错误的测试用例，不清楚原实现失败的根因。修改后的binary_search函数如下：

def binary_search(self,low,high):
        '''
        Implementing the binary search algorithm with distinct numbers on a sorted input.
        '''
        
        #trivial case
        if (low>=high-1) and self.array[low]!=self.query:
            return -1
        
        elif (self.query<self.array[low]) or (self.query>self.array[high-1]):
            return -1
            
        
        else:
            m=low+(high-low)//2
            if self.array[low]==self.query:
                return low
            elif (self.array[m-1]>=self.query):
                return self.binary_search(low,m)
            elif self.array[m]<=self.query:   
                return self.binary_search(m,high)
            elif self.array[high-1]==self.query:
                return high-1
            else: 
                return -1

内容的提问来源于stack exchange，提问作者bbt_wb