โจทย์
มีคลาส TestArray ที่มี Private Array และ Methods:
length()- คืนความยาวcompare(l, r, x, y)- เปรียบเทียบผลรวม Subarray [l..r] กับ [x..y] คืน 1, 0, -1
ต้องหา Index ของค่าสูงสุดในอาร์เรย์โดยใช้เฉพาะ Methods นี้
ตัวอย่าง: array = [8, 4, 2, 12, 11, 8, 4, 2, 7] → Output: 3 (ค่า 12 อยู่ Index 3)
อัลกอริธึม (Binary Search แบบปรับ)
- ใช้ Binary Search บนช่วง [low, high]
- คำนวณ mid แบบพิเศษ:
(low+high+1)//2 - เปรียบเทียบครึ่งซ้ายและขวาโดยใช้
compare() - ปรับ low/high ตามผลลัพธ์ จน low == high
โค้ด Python
class TestArray:
def __init__(self, array) -> None:
self.__arr = array
def length(self):
return len(self.__arr)
def compare(self, l, r, x, y):
val1 = sum(self.__arr[l:r+1])
val2 = sum(self.__arr[x:y+1])
if val1 > val2: return 1
elif val1 == val2: return 0
else: return -1
def solve(reader):
n = reader.length()
low, high = 0, n - 1
while low < high:
mid = (low + high + 1) // 2
if (low + high + 1) % 2 == 0:
res = reader.compare(low, mid-1, mid, high)
if res == 1: high = mid - 1
else: low = mid
else:
res = reader.compare(low, mid-1, mid+1, high)
if res == 1: high = mid - 1
elif res == -1: low = mid + 1
else: return mid
if high == low: return high
return -1
arr_ob = TestArray([8, 4, 2, 12, 11, 8, 4, 2, 7])
print(solve(arr_ob)) # Output: 3
Input / Output
Input: [8, 4, 2, 12, 11, 8, 4, 2, 7]
Output: 3
