bsearch.py

class Record:
    def __init__(self, key):
        self.key = key

    def __str__(self):
        return str(self.key)

class OrderedRecordArray:
    def __init__(self, initial_capacity):
        self.__a = [None] * initial_capacity
        self.__nItems = 0

    def size(self):
        return self.__nItems

    def get(self, index):
        if 0 <= index < self.__nItems:
            return self.__a[index]
        raise IndexError("Index out of bounds")

    def find(self, search_key):
        lower_bound = 0
        upper_bound = self.__nItems - 1

        while lower_bound <= upper_bound:
            cur = (lower_bound + upper_bound) // 2
            if self.__a[cur].key == search_key:
                return cur
            elif self.__a[cur].key < search_key:
                lower_bound = cur + 1
            else:
                upper_bound = cur - 1
        return -1

    def delete(self, search_key):
        """
        Deletes all records matching search_key. 
        Returns True if at least one was deleted, False if none were found.
        """
        deleted_any = False
        
        while True:
            # Find any instance of the search_key using binary search
            idx = self.find(search_key)
            
            # If not found, exit the loop
            if idx == -1:
                break
                
            # If found, shift the elements to the left to delete it
            for k in range(idx, self.__nItems - 1):
                self.__a[k] = self.__a[k + 1]
                
            self.__nItems -= 1
            self.__a[self.__nItems] = None # Clear the last duplicate slot
            deleted_any = True
            
        return deleted_any

    def insert(self, item):
        if self.__nItems >= len(self.__a):
            raise Exception("Array is full")
            
        j = 0
        while j < self.__nItems and self.__a[j].key < item.key:
            j += 1
            
        for k in range(self.__nItems, j, -1):
            self.__a[k] = self.__a[k - 1]
            
        self.__a[j] = item
        self.__nItems += 1

    def __str__(self):
        return ", ".join(str(self.__a[i]) for i in range(self.__nItems))

# --- Testing Program ---

if __name__ == "__main__":
    print("Testing OrderedRecordArray with duplicate keys:")
    arr = OrderedRecordArray(20)

    # Insert records, including duplicates
    records = [15, 10, 20, 10, 5, 10, 25, 10]
    for r in records:
        arr.insert(Record(r))

    print(f"Initial Array:              {arr}")

    # Test 1: Delete a key that exists multiple times (10 is in there 4 times)
    arr.delete(10)
    print(f"After deleting 10s:         {arr}")

    # Test 2: Delete a key that exists only once (25)
    arr.delete(25)
    print(f"After deleting 25:          {arr}")

    # Test 3: Delete a key that is at the very beginning (5)
    arr.delete(5)
    print(f"After deleting 5:           {arr}")

    # Test 4: Delete a key that does NOT exist in the array (99)
    result = arr.delete(99)
    print(f"After deleting 99 (Absent): {arr} | Delete Result: {result}"