ค้นหาองค์ประกอบที่ขาดหายไปในอาร์เรย์ที่เรียงลำดับของตัวเลขต่อเนื่องกันใน Python

สมมติว่าเรามีอาร์เรย์ A จำนวน n ตัวเลขที่ไม่ซ้ำกัน องค์ประกอบ n เหล่านี้มีอยู่ในอาร์เรย์โดยเรียงลำดับจากน้อยไปมาก แต่มีองค์ประกอบที่ขาดหายไปหนึ่งรายการ เราต้องหาองค์ประกอบที่ขาดหายไป

ดังนั้น หากอินพุตเป็น A =[1, 2, 3, 4, 5, 6, 7, 9] ผลลัพธ์จะเป็น 8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• ซ้าย :=0

• ขวา :=n - 1

• กลาง :=0

• ในขณะที่ right> left ทำ

  • กลาง :=ซ้าย +(ขวา - ซ้าย) / 2

  • ถ้า A[mid] - mid เหมือนกับ A[0] แล้ว

    • ถ้า A[กลาง + 1] - A[กลาง]> 1 แล้ว

      • กลับ A[กลาง] + 1

    • มิฉะนั้น

      • ซ้าย :=กลาง + 1

  • มิฉะนั้น

    • ถ้า A[กลาง] - A[กลาง - 1]> 1 แล้ว

      • กลับ A[กลาง] - 1

    • มิฉะนั้น

      • ขวา :=กลาง - 1

• กลับ -1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def search_missing_item(A):
   n = len(A)
   left, right = 0, n - 1
   mid = 0
   while (right > left):
      mid = left + (right - left) // 2
   if (A[mid] - mid == A[0]):
      if (A[mid + 1] - A[mid] > 1):
         return A[mid] + 1
      else:
         left = mid + 1
      else:
         if (A[mid] - A[mid - 1] > 1):
            return A[mid] - 1
         else:
            right = mid - 1
   return -1

A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))

อินพุต

[1, 2, 3, 4, 5, 6, 7, 9]

ผลลัพธ์

8