ئه‌لگۆریتمی به‌دواگه‌ڕانی باینه‌ری

ئێمه هه‌موومان له ژیانماندا تووشی مه‌سه‌له‌ی ڕیزبه‌ند کردن بووین. واته دۆخێک پێشهاتووه که پێویست بووه کۆمه‌ڵێک بابه‌ت (وه‌ک پاره، ژماره، کارتی یاری و لیستی نمره و ناوونیشان ، هتد) به ڕه‌چاوگرتنی پێوه‌رێکی دیاریکراو به‌دوای یه‌کدا ڕیز بکه‌ین و ڕێک و پێکیان بکه‌ین. بۆ نموونه‌، زۆر جار پێویست ده‌بێت ناوه‌ڕۆکی نێو جزدانه‌که‌مان ڕێک و پێک بکه‌ین و له‌ شێواوی ده‌ری بێنین. ئه‌م کاره جگه له‌وه‌ی تۆزێک باری جزدانه‌که‌مان سووک ئه‌کات، ده‌بێته هۆی ئه‌وه‌ی له داهاتوودا بتوانین خێراتر پاره یا بابه‌تی پێویستی تێدا بدۆزینه‌وه. به گشتی ئێمه حه‌زمان له ڕێکوپێکییه چونکه ئه‌رکی دۆزینه‌وه خێراتر ده‌کات. ئه‌مه ڕاستییه‌که هه‌موو که‌س له ژیانیدا ئه‌زموونی کردووه. به‌ڵام وێڕای گرنگی ڕێکوپێکی، له‌م ده‌وروزه‌مانه‌دا که‌متر پێویست ده‌بێ بۆخۆمان شته‌کان ڕێکوپێک بکه‌ین. ئێستاکه زۆر له‌و بابه‌تانه‌ی ئیشی پێده‌که‌ین له کۆمپیوته‌ره‌کاندا خزن ده‌کرێن و سۆفتوێره‌‌کان له بری ئێمه داتاکان و ژماره‌کان و لیستی ناوونیشانه‌کانمان بۆ ڕیزبه‌ند ده‌که‌ن. به‌ڵام کۆمپیوته‌ره‌کان به بێ ئه‌وه‌ی پرۆگرامییان پێ بدرێت، بۆخۆیان ناتوانن ئه‌م کارانه بکه‌ن. واته ده‌بێ (به زمانی سه‌ره‌تایی خۆیان) پێیان بوترێ چۆن ئه‌رکێک جێبه‌جێ بکه‌ن. بۆ نموونه کاتێک ده‌مانه‌وێ کۆمه‌ڵێک ژماره‌مان بۆ ڕیزبه‌ند بکه‌ن، ده‌بێ ڕێوشوێن یا پرۆگرامی ڕیزبه‌ندکردنیشیان پێ بده‌ین. بۆ ئه‌م ئامانجه، سه‌ره‌تا پێویسته خۆمان بزانین چۆن کۆمه‌ڵێک ژماره له که‌مه‌وه بۆ زۆر ڕیزبه‌ند بکه‌ین. واته به زمانێکی ساده و ڕوون که خۆمان لێی تێ بگه‌ین و ڕاستییه‌که‌ی بتوانین هه‌ڵبسه‌نگێنین ڕێوشوێن یا ئه‌لگۆریتمی ئه‌م کاره دابڕێژین. به گشتی له دونیای بیرکاری و کامپیوته‌ردا، به‌ وه‌سفی هه‌نگاو به هه‌نگاوی جێبه‌جێکردنی ئه‌رکێک ده‌وترێت ئه‌لگۆریتم.

ئه‌لگۆریتم به گشتی وه‌سفی هه‌نگاو به هه‌نگاوی جێبه‌جێکردنی ئه‌رکێکه. هه‌موو ئه‌لگۆریتمێک کۆمه‌ڵێک داتا وه‌رده‌گرێ و پاش پرۆسس کردنی داتاکان کۆمه‌ڵێک داتای تر وه‌ک به‌رهه‌م ئه‌داته‌ ده‌ره‌وه. بۆ نموونه شێوازی دروستکردنی هه‌موو خۆراکێک جۆرێک ئه‌لگۆریتمه که کۆمه‌ڵێک که‌ره‌سته‌‌ی پێویست (وه‌ک گۆشت و پیاز و برنج و زه‌یت و شتی تره) وه‌رده‌گرێ و بریتییه له وه‌سفی زنجیره هه‌نگاوێک بۆ لێنانی ئه‌و خۆراکه.

 

بۆ نموونه‌یه‌کی کۆمپیوته‌ری بڕواننه مه‌سه‌له‌ی به‌دواگه‌ڕان. لیستێک بریتی له ژماره‌مان پێدراوه و ده‌مانه‌وێ بزانین ئاخۆ ئه‌م لیسته ژماره‌یه‌کی داواکراو وه‌ک ی تێدایه یان نا. ڕێگایه‌کی ڕاسته‌وخۆ بۆ جێبه‌جێکردنی ئه‌م ئه‌رکه ئه‌وه‌یه که لیسته‌که له سه‌ره‌تاوه تا کۆتایی پشکنین بکه‌ین و ژماره‌کان هه‌موو یه‌که به یه‌که تاقی بکه‌ینه‌وه تا ئه‌گه‌ین به ژماره‌یه‌ک که یه‌کسانه به یا ئه‌وه‌یکه بۆمان ده‌رده‌که‌وێ که ئه‌م لیسته‌ ژماره‌یه‌ک وه‌ک ی تێدا نییه. به‌م ڕێگاچاره‌یه ده‌وترێت به‌دواگه‌ڕانی هێڵی چونکه له‌وه‌ده‌چێ ته‌واوی خاڵه‌کانی سه‌ر هێڵێک بپێوین. به زمانی پرۆگرامی کۆمپیوته‌ری، ئه‌م ڕێگاچاره‌یه ده‌توانین به‌م شێوه‌یه بنووسین.

---

Input: A(1), …,A(n), x
For i=1 to n

If(A(i) == x) Stop and Return i
End For

Return x was not found

---

 

بڕوانن که ئه‌م ئه‌لگۆریتمه کۆمه‌ڵێک داتا وه‌رده‌گرێ که بریتیه له لیستی و ژماره‌یه‌کی داواکراو . ئاڵقه‌یه‌کی Forی هه‌یه که له هه‌ر پێداچوونه‌وه‌یدا تێستێکی یه‌کسانبوون نێوان خانه‌یه‌کی لیسته‌که و ژماره‌ی  به‌ڕێوه‌ده‌بات.  ئه‌مه ئه‌لگوریتمێکی ساده‌یه و تێگه‌یشتنه‌که‌ی زۆر ئاسانه به‌ڵام له ڕاستی دا ئه‌مه ئه‌لگۆریتمێکی زۆر باش نییه. چونکه هه‌ر جار بمانهه‌وێ ژماره‌یه‌ک بدۆزینه‌وه، ده‌بێ له‌سه‌رڕا ته‌واوی لیسته‌که‌ پشکنین بکه‌ین. واته له خراپترین حاڵه‌تدا ده‌بێ ته‌واوی لیسته‌که بگه‌ڕێین. دۆخه‌که‌ له کاتێک ده‌چێ که له ژوورێکی شپرز و شێواو داین و بۆ تاگۆره‌وییه‌کی ون ده‌گه‌ڕێین! ده‌بێ هه‌موو سووچ و قوژبنێکی ژووره‌که‌ پشکنین بکه‌ین.

هاوشێوه‌ی ئه‌م دۆخه، لێره‌ش بۆ هه‌ر پرسی دۆزینه‌وه نزیک به کرداری به‌راوردکردن ده‌بێ ئه‌نجام بدرێت. ئه‌گه‌ر درێژه‌ی لیسته‌که که‌م بێت (که‌ل و په‌لی ناو ژووره‌که‌ که‌م بێت)، ئه‌مه کێشه‌یه‌کی ئه‌وتۆ نییه به‌ڵام ئه‌گه‌ر ڕه‌قه‌مێکی یه‌کجار گه‌وره بێت، ئه‌مه ئه‌توانێ کاتێکی زۆر ببات. وه‌ک نموونه‌ی ژووری شپرز و کێشه‌ی په‌یداکردنی تاگۆره‌وی، لێره‌ش چاره‌سه‌ری مه‌سه‌له‌که‌ له ڕێکوپێک کردن و ڕیزبه‌ندکردنی لیستی ژماره‌کاندایه. ئیتر مه‌سه‌له‌که‌مان ده‌بێته حه‌ڵی مه‌سه‌له‌ی به‌دواگه‌ڕانی ژماره‌یه‌ک له لیستێکی ڕیزبه‌ندکراودا و ئه‌مه پرۆسه‌ی دۆزینه‌وه گه‌لێک خێراتر ده‌کات. هه‌ڵبه‌ت ئه‌گه‌ر ژماره‌یه‌کی ڕه‌مه‌کیمان بده‌نێ هێشتا نازانین له کوێی لیسته‌که‌دا بۆی بگه‌ڕێین، به‌ڵام ئه‌لگۆریتمێکی ساکار هه‌یه که خێرا شوێنی ڕه‌قه‌مه‌که‌ ده‌دۆزێته‌وه (ئه‌گه‌ر له لیسته‌که‌دا هه‌بێت). ئه‌م ئه‌لگۆریتمه ناسراوه به به‌دواگه‌ڕانی باینه‌ری.

بۆ جێبه‌جێکردنی زۆربه‌ی ئه‌رکه‌کان چه‌ندین ڕێگای جیاواز هه‌یه. له زانستی کومپیوته‌ردا ئێمه حه‌ز ده‌که‌ین ئه‌لگۆریتمێک بدۆزینه‌وه که به ژماره هه‌نگاوی که‌م و به که‌مترین پرۆسس بگاته ئامانجی خۆی. به ئه‌مه ده‌وترێ ئه‌لگوریتمێکی گورج و خێرا.

 ئه‌لگۆریتمی به‌دواگه‌ڕانی باینه‌ری بۆ په‌یداکردنی ژماره‌یه‌ک، شوێنی ژماره‌که‌ به زنجیره‌یه‌ک پرسیار که وه‌ڵامه‌کانیان ئه‌رێ یا نایه، ئه‌دۆزێته‌وه.

ئه‌مه وه‌کوو ئه‌و یارییه‌ وایه که من شتێکم له زه‌ین دایه و تۆ ده‌بێ به کۆمه‌ڵێک پرسیار که وه‌ڵامه‌که‌یان ته‌نیا ئه‌رێ یا نایه په‌یدای بکه‌یت. ئه‌لگۆریتمی به‌دواگه‌ڕانی باینه‌ری به‌م شێوه ده‌ست پێده‌کات: ئایا  له زۆربه‌ی ژماره‌کان گه‌وره‌تره؟ واته ئایا له ژماره‌ی گه‌وره‌تره؟ ئه‌گه‌ر وه‌ڵامه‌که‌ی به‌لێ بێت، ئاشکرایه ده‌بێ له نێوه‌ی سه‌رووی لیسته‌که‌دا بێت و ئه‌گه‌ر وه‌ڵامه‌که‌ی نا بێت، ده‌بێ له نیوه‌ی خوارووی لیسته‌که‌دا بێت. ئه‌گه‌رێکی تریش هه‌یه : له‌گه‌ڵ یه‌کسانه و له‌م حاڵه‌ته‌دا پرۆسه‌ی به‌دواگه‌ڕان کۆتایی پێدێت. به‌ڵام ئه‌گه‌ر وانه‌بوو، ئه‌لگۆریتمه‌که له‌ نیوه‌‌ی سه‌ره‌وه یا له نیوه‌ی خواره‌وه‌ به هه‌مان شێوه به پشکنینی ناوقه‌دی لیسته‌که له شوێنی نزیک ده‌بێته‌وه. ئه‌م پرۆسه‌یه ده‌توانین وه‌ک پرۆگرامێک به‌م شێوه‌یه بنووسین.

---

Input: A[L,R], x

Binary-Search (A[L,R],x)

i=(L+R)/2

If A(i) == x then Output i and Terminate

If L=R Output “NOT FOUND” and Terminate

If A[i] < x then Binary-Search(A[i+1,R], x)

If A[i] > x then Binary-Search(A[L,i-1],x)

---

 

بڕوانن لێره ئه‌لگۆریتمه‌که لیستێک ژماره وه‌ک وه‌رده‌گرێت. L و R سنووری ده‌سپێک و کۆتایی لیسته‌که‌ن. ئه‌لگۆریتمه هه‌ر جار ژماره‌ی ناوه‌ڕاستی لیسته‌که پشکنین ده‌کات و به‌م شێوه‌یه بازنه‌ی گه‌ڕانه‌که چکۆله‌تر ده‌بێته‌وه.

لێره ئه‌م پرسیاره دێته گۆڕێ که به‌دواگه‌ڕانی باینه‌ری بۆ هه‌ر پرسێکی به‌دواگه‌ڕان له خراپترین حاڵه‌تدا  پێویستی به چه‌ند تێستی به‌راورد کردن هه‌یه. دیاره به پێی وێنه‌ی خواره‌وه ژماری زۆرترین به‌راورد یه‌کسانه به باڵای دره‌ختی پرسیاره‌کان، واته ژماری پله‌کانی دره‌خته‌که که بریتییه له ژماری ئاسته‌کان له ڕه‌گی دره‌خته‌که تا ده‌چێته سه‌ر ئاستی گه‌ڵاکان (بڕوانن دره‌خته‌که سه‌راوبنه!). به وته‌یه‌کی تر، چه‌ند جار ده‌توانین ژماره‌ی دووله‌ت بکه‌ین به مه‌رجێک ئه‌ندازه‌ی له‌تێکیان لانیکه‌م بێت؟ به شیکارییه‌کی ئاسایی بۆمان ده‌رده‌که‌وێ وه‌ڵامی ئه‌م پرسیاره  له   که‌متره. ئاشکرایه ئه‌مه له ژماری به‌راورده‌کانی به‌دواگه‌ڕانی هێڵی هێجگار باشتره.

بۆ هه‌ڵسه‌نگاندنی خێرایی ئه‌لگۆریتمه‌کان چه‌ندین پێوه‌ر هه‌یه. بۆ نموونه به پێوه‌ری ئاڵۆزی خراپترین حاڵه‌ت، ئه‌لگوریتمێک خێرایه که له خراپترین حاڵه‌تدا به که‌مترین ژماری هه‌نگاو بگاته ئامانج. هه‌ر وه‌ک دیتمان ئه‌لگۆریتمی به‌دواگه‌ڕانی هێڵی له خراپترین حاڵه‌تدا پێویستی به ژماری به‌راوردکردن هه‌یه له حاڵێکدا ئه‌لگۆریتمی به‌دواگه‌ڕانی باینه‌ری له خراپترین حاڵه‌تدا پێویستی به ژماری به‌راورد کردن هه‌یه. که‌وایه ئه‌لگۆریتمی به‌دواگه‌ڕانی باینێری له ئه‌لگۆریتمی به‌دواگه‌ڕانی هێڵی خێراتره. 

له به‌شی داهاتووی ئه‌م وتاره‌دا، ده‌چینه سه‌رباسی ڕیزبه‌ندکردن و چه‌ند ئه‌لگۆریتمی خێرا بۆ ڕیزبه‌ندی شیکار ده‌که‌ین.

نووسراوه‌ له‌لایه‌ن
tcsbirkar