ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่ผ่านๆ มา แต่วัตถุที่เราทำการค้นหาจะแตกต่างจากข้ออื่นมาก

เพื่อความสะดวก เราจะกำหนดให้อะเรย์ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

A\,

และ

B\,

มีช่อง

A[0]\,

และ

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 226197193 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Wed, 21 Jan 2026 17:13:09 GMT Sensitive client information IP address: 158.108.32.49

โดยที่

A[0]=-\infty \,

และ

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 276599236 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Wed, 21 Jan 2026 17:13:09 GMT Sensitive client information IP address: 158.108.32.49

กล่าวคือ

A[0]\,

และ

B[0]\,

จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด แต่เราจะไม่นับว่าช่องที่เพิ่มมาใหม่นี้เป็นส่วนหนึ่งของอะเรย์

เราจะพิสูจน์ข้อความสามข้อความต่อไปนี้

lemma 1: ถ้า $i\,$ และ $j\,$ เป็นจำนวนเต็มที่

$0\leq i\leq m\,$ และ
$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 279219520 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Wed, 21 Jan 2026 17:13:11 GMT Sensitive client information IP address: 158.108.32.49$ และ
$i+j=k-1\,$ และ
$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 280332173 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Wed, 21 Jan 2026 17:13:12 GMT Sensitive client information IP address: 158.108.32.49$ และ
$B[j+1]>A[i]\,$

แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ในอะเรย์ $A\,$ และ $B\,$ คือ $\min(A[i+1],B[j+1])\,$

พิสูจน์: ให้ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

x\,

เป็นจำนวนที่น้อยกว่าระหว่าง

A[i+1]\,

และ

B[j+1]\,

แล้วจะได้ว่ามีจำนวน

i\,

ตัวใน

A\,

ที่น้อยกว่า

x\,

และจำนวน

j\,

ตัวใน

B\,

ที่น้อยกว่ามัน ฉะนั้นมีจำนวน

i+j=k-1\,

ตัวใน

A\,

และ

B\,

ที่น้อยกว่ามันพอดี ดังนั้น

x\,

เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่

k\,

พอดี

lemma 2: ถ้า $A[i+1]\,$ คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ใน $A\,$ และ $B\,$ โดยที่ $0\leq i\leq m\,$ แล้ว หากให้ $j=k-1-i\,$ แล้ว เราจะได้ว่า $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$

พิสูจน์: เนื่องจาก $A[i+1]\,$ เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ดังนั้นจะต้องมีสมาชิกใน $A\,$ และ $B\,$ ที่น้อยกว่ามัน $k-1\,$ ตัวพอดี และเนื่องจากมีสมาชิกที่น้อยกว่า $A[i+1]\,$ อยู่ $i\,$ ตัวในอะเรย์ $A\,$ จะต้องมีสมาชิกที่้น้อยกว่า $A[i+1]\,$ อยู่ $k-1-i=j\,$ ตัวใน $B\,$ ซึ่งนี่หมายความว่า $A[i+1]>B[j]\,$

อนึ่ง เราจะได้ว่า $B[j+1]>A[i+1]>A[i]\,$ ด้วย ฉะนั้น lemma เป็นจริง

lemma 3: ถ้า $B[j+1]\,$ คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ใน $A\,$ และ $B\,$ โดยที่ $0\leq j\leq n\,$ แล้ว หากให้ $i=k-1-j\,$ แล้ว เราจะได้ว่า $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$

พิสูจน์: ใช้วิธีพิสูจน์เดียวกันกับ lemma 2

สังเกตว่า lemma 2 และ lemma 3 เป็น converse ของ lemma 1 ฉะนั้นเราสามารถสรุปได้ว่า

Proposition 4: เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ $k\,$ ในอะเรย์ $A\,$ และ $B\,$ ได้โดยการหาจำนวนเต็ม $i\,$ และ $j\,$ ที่ทำให้ (1) $i+j=k-1\,$ และ (2) $A[i+1]>B[j]\,$ และ (3) $B[j+1]>A[i]\,$ แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง $A[i+1]\,$ และ $B[j+1]\,$

(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี $i\,$ และ $j\,$ เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)

อัลกอริทึม

อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ $(i,j)\,$ โดยที่ $i+j=k-1\,$ โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก $k\,$ ตัวด้วยกัน ได้แต่ $(0,k-1),(1,k-2),(2,k-3),\ldots ,(k-2,1),(k-1,0)\,$

สำหรับวัตถุแต่ละอัน เราจะทำการเปรียบเทียบสองครั้ง ได้แก่ (1) เปรียบเทียบ $A[i+1]\,$ กับ $B[j]\,$ และ (2) เปรียบเทียบ $B[j+1]\,$ กับ $A[i]\,$ โดยการเปรียบเทียบนี้เกิดผลได้ 3 แบบด้วยกัน

$A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$ : ในกรณีเราจะได้ว่าเราหา $(i,j)\,$ ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้

$A[i+1]>B[j]\,$ และ $B[j+1]<A[i]\,$ : ในกรณีเราพบว่าสำหรับคู่ลำดับ $(i',j')\,$ อื่นๆ ที่ $i'>i\,$ เราจะได้ว่า $A[i'+1]>A[i+1]>B[j]>B[j']\,$ และ $B[j'+1]\leq B[j]<A[i]<A[i']\,$ ด้วยเหตุนี้ $(i',j')\,$ จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ $(i',j')\,$ โดยที่ $i'>i\,$ ออกจากวัตถุที่เป็นไปได้ทั้งหมด

$A[i+1]<B[j]\,$ และ $B[j+1]>A[i]\,$ : ในกรณีเราพบว่าสำหรับคู่ลำดับ $(i',j')\,$ อื่นๆ ที่ $i'<i\,$ เราจะได้ว่า $A[i'+1]<A[i+1]<B[j]<B[j']\,$ และ $B[j'+1]>B[j+1]>A[i]>A[i']\,$ ด้วยเหตุนี้ $(i',j')\,$ จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ $(i',j')\,$ โดยที่ $i'<i\,$ ออกจากวัตถุที่เป็นไปได้ทั้งหมด

จากแนวคิดข้างต้น เราสามารถเขียน pseudocode ของอัลกอริืทึมได้ดังต่อไปนี้

<geshi lang="c"> Search(A, B, k) {

   i_left = 0
   i_right = k-1

   while i_left <= i_right do
   {
      i = (i_left + i_right) / 2
      j = k - 1 - i

      if A[i+1] > B[j] and B[j+1] > A[i] then
           return min(A[i+1], B[j+1])
      else if A[i+1] > B[j] and B[j+1] < A[i] then
           i_right = i-1
      else if A[i+1] < B[j] and B[j+1] > A[i] then
           i_left = i+1
   }

} </geshi>

เนื่องจากในการเช็คเงื่อนไขแต่ละครั้งเราสามารถตัดวัตถุที่เป็นไปได้ออกประมาณครึ่งหนึ่ง เราจะได้ว่าจะมีการวนลูปใน pseudocode อย่างมาก $O(\log k)=O(\log(m+n))=O(\log m+\log n)\,$ ครั้ง ฉะนั้นอัลกอริทึมข้างบนจึงทำงานภายในเวลา $O(\log n+\log m)\,$ ตามต้องการ

418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4

Error

Error

อัลกอริทึม

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ