ሁለትዮሽ ፍለጋ ከመስመር ፍለጋ
የመስመር ፍለጋ፣ እንዲሁም ተከታታይ ፍለጋ በመባል የሚታወቀው ቀላሉ የፍለጋ ስልተ ቀመር ነው። በዝርዝሩ ውስጥ ያሉትን እያንዳንዱን ንጥረ ነገሮች በማጣራት በአንድ ዝርዝር ውስጥ የተወሰነ እሴት ይፈልጋል። ሁለትዮሽ ፍለጋ በተደረደሩ ዝርዝር ውስጥ የተወሰነ እሴት ለማግኘትም የሚያገለግል ዘዴ ነው። የሁለትዮሽ ፍለጋ ዘዴ የተፈተሹትን ንጥረ ነገሮች ብዛት በግማሽ ይቀንሳል (በእያንዳንዱ ድግግሞሽ)፣ የተሰጠውን ንጥል በዝርዝሩ ውስጥ ለማግኘት የሚፈጀውን ጊዜ ይቀንሳል።
ሊኒያር ፍለጋ ምንድነው?
የመስመር ፍለጋ ቀላሉ የመፈለጊያ ዘዴ ነው፣ ይህም በዝርዝሩ ውስጥ ያለውን እያንዳንዱን የተወሰነ አካል እስኪያገኝ ድረስ በቅደም ተከተል ያረጋግጣል።የመስመራዊ ፍለጋ ዘዴ ግብአት ቅደም ተከተል (እንደ ድርድር፣ ስብስብ ወይም ሕብረቁምፊ) እና መፈለግ ያለበት ንጥል ነው። የተጠቀሰው ንጥል በቀረበው ቅደም ተከተል ውስጥ ከሆነ ወይም በቅደም ተከተል ካልሆነ የውሸት ውጤት እውነት ነው. ይህ ዘዴ የተገለጸው ንጥል እስኪገኝ ድረስ በዝርዝሩ ውስጥ ያሉትን እያንዳንዱን እቃዎች ስለሚፈትሽ በጣም በከፋ ሁኔታ ውስጥ አስፈላጊውን አካል ከማግኘቱ በፊት በዝርዝሩ ውስጥ ያሉትን ሁሉንም ንጥረ ነገሮች ያልፋል። የመስመራዊ ፍለጋ ውስብስብነት o(n) ነው። ስለዚህ በትላልቅ ዝርዝሮች ውስጥ ንጥረ ነገሮችን ሲፈልጉ ለመጠቀም በጣም ቀርፋፋ ነው ተብሎ ይታሰባል። ግን ይህ በጣም ቀላል እና ለመተግበር ቀላል ነው።
ሁለትዮሽ ፍለጋ ምንድነው?
ሁለትዮሽ ፍለጋ እንዲሁ በተደረደረ ዝርዝር ውስጥ የተወሰነ ንጥል ነገር ለማግኘት የሚያገለግል ዘዴ ነው። ይህ ዘዴ የሚጀምረው የተፈለገውን ንጥረ ነገር በዝርዝሩ መካከል ከሚገኙት ንጥረ ነገሮች ጋር በማነፃፀር ነው. ንፅፅሩ ሁለቱ አካላት እኩል መሆናቸውን ከወሰነ ዘዴው ይቆማል እና የንጥሉን ቦታ ይመልሳል። የተፈለገው ኤለመንት ከመካከለኛው ኤለመንት የሚበልጥ ከሆነ ከተደረደሩት ዝርዝር ውስጥ የታችኛውን ግማሽ ብቻ በመጠቀም ዘዴውን እንደገና ይጀምራል.የተፈለገው ኤለመንት ከመካከለኛው ኤለመንት ያነሰ ከሆነ, ከተደረደረው ዝርዝር ውስጥ ከፍተኛውን ግማሽ ብቻ በመጠቀም ዘዴውን እንደገና ይጀምራል. የተፈለገው አካል በዝርዝሩ ውስጥ ከሌለ፣ ዘዴው ያንን የሚያመለክት ልዩ እሴት ይመልሳል። ስለዚህ የሁለትዮሽ የፍለጋ ዘዴ በንፅፅር (በእያንዳንዱ ድግግሞሽ) የንፅፅርን ብዛት በግማሽ ይቀንሳል። ስለዚህ፣ የሁለትዮሽ ፍለጋ በሎጋሪዝም ጊዜ ይሰራል ይህም የ o(log n) አማካኝ ኬዝ አፈጻጸምን ያስከትላል።
በሁለትዮሽ ፍለጋ እና በመስመር ፍለጋ መካከል ያለው ልዩነት ምንድነው?
ምንም እንኳን ሁለቱም መስመራዊ ፍለጋ እና ሁለትዮሽ ፍለጋ የፍለጋ ዘዴዎች ቢሆኑም ብዙ ልዩነቶች አሏቸው። ሁለትዮሽ ፍለጋ በተደረደሩ ዝርዝሮች ላይ ቢሰራም፣ የላይነር ፍለጋ ባልተደረደሩ ዝርዝሮች ላይም ሊሠራ ይችላል። ዝርዝርን መደርደር በአጠቃላይ የ n log n አማካይ የጉዳይ ውስብስብነት አለው። መስመራዊ ፍለጋ ከሁለትዮሽ ፍለጋ ይልቅ ለመተግበር ቀላል እና ቀላል ነው። ነገር ግን መስመራዊ ፍለጋ በ o(n) አማካኝ የጉዳይ አፈፃፀሙ ምክንያት ከትላልቅ ዝርዝሮች ጋር ለመጠቀም በጣም ቀርፋፋ ነው።በሌላ በኩል, ሁለትዮሽ ፍለጋ ከትላልቅ ዝርዝሮች ጋር ጥቅም ላይ ሊውል የሚችል የበለጠ ቀልጣፋ ዘዴ ተደርጎ ይቆጠራል. ነገር ግን የሁለትዮሽ ፍለጋን መተግበር በጣም አስቸጋሪ ሊሆን ይችላል እና አንድ ጥናት እንደሚያሳየው ትክክለኛው የሁለትዮሽ ፍለጋ ኮድ ከሃያ መጽሐፍት ውስጥ በአምስቱ ውስጥ ብቻ ሊገኝ ይችላል።
