สมมติว่าเรามีรายการองค์ประกอบที่เรียกว่า nums ซึ่งรายการทั้งหมดไม่ซ้ำกัน และเรียงลำดับจากน้อยไปมาก เราต้องหาค่าต่ำสุด i ที่ nums[i] =i หากเราไม่พบวิธีแก้ปัญหาใดๆ ให้คืนค่า -1 เราต้องแก้ปัญหานี้ในเวลา O(log(n))
ดังนั้น หากอินพุตเท่ากับ nums =[-4, -1, 2, 3, 8] เอาต์พุตจะเป็น 2 เพราะทั้ง nums[2] =2 และ nums[3] =3 แต่ 2 มีขนาดเล็กกว่า
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=-1, lhs :=0, rhs :=ขนาดของ nums - 1
-
ในขณะที่ lhs <=rhs ทำ
-
กลาง :=ชั้นของ (lhs + rhs) / 2
-
ถ้า nums[mid] เท่ากับ mid แล้ว
-
ret :=กลาง
-
-
ถ้า nums[mid]>=mid แล้ว
-
rhs :=กลาง - 1
-
-
มิฉะนั้น
-
lhs :=กลาง + 1
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(nums):
ret = -1
lhs = 0
rhs = len(nums) - 1
while lhs <= rhs:
mid = (lhs + rhs) // 2
if nums[mid] == mid:
ret = mid
if nums[mid] >= mid:
rhs = mid - 1
else:
lhs = mid + 1
return ret
nums = [-4, -1, 2, 3, 8]
print(solve(nums)) อินพุต
[-4, -1, 2, 3, 8]
ผลลัพธ์
2
