Binary Search

ကၽြန္ေတာ္တို႔ Sequential Searching မွာတုန္းက array ဟာ sorting စီထားျခင္း မရွိပါဘူး။ သို႔ေပမယ့္ Binary Search ကို အသံုးျပဳေတာ့မယ္ဆိုရင္ array ဟာ မျဖစ္မေန sorting စီထားမွသာ ျဖစ္ပါမယ္။

  • Binary Search ဟာ sorting စီထားသည့္ array ကို အလယ္ကို ေထာက္လိုက္ပါတယ္။
  • mid value က ရွာမယ့္ value နဲ႔ တူခဲ့ရင္ ရွာေတြ႕ၿပီေပါ့။
  • အကယ္၍ မေတြ႕ခဲ့ရင္ mid value က ရွာမယ့္ value နဲ႔ ငယ္လား ႀကီးလာစစ္တယ္။
  • အကယ္၍ ငယ္ခဲ့ရင္ mid value ေရွ႕က အခန္းက ေနာက္ဆံုး အခန္းျဖစ္ၿပီး ေရွ႕ဆံုးက အခန္းက ပထမ အခန္းျဖစ္တယ္။ ၿပီရင္ အလယ္ကို ျပန္ေထာက္ၿပီး ရွာပါတယ္။
  • အကယ္၍ ႀကီးခဲ့ရင္ ပထမဆံုး အခန္းက mid value ရဲ႕ ေနာက္က အခန္းျဖစ္ၿပီးေတာ့ ေနာက္ဆံုး အခန္း နဲ႔ ပထမဆံုး အခန္းရဲ႕ အလယ္ကို ျပန္ေထာက္ၿပီး ရွာပါတယ္။

သေဘာတရားေလးက ရွင္းပါတယ္။ ဒါေၾကာင့္ သူက sorting စီထားဖို႔ လိုပါတယ္။ အခန္းေတြ အကုန္မသြားေတာ့ပဲ အလယ္အခန္းက ရွာေဖြ သြားတာပါ။

ေသခ်ာနားလည္ သြားေအာင္ ေအာက္က ပံုေလးကို ၾကည့္ၾကည့္ပါ။

ပထမပံုကေတာ့ search လုပ္သည့္ အခါမွာ ရွာေတြ႕သည့္ flow ေလးပါ။

ဒုတိယပံုကေတာ့ ရွာမေတြ႕သည့္ flow ပါ။ အကယ္၍ first ကသာ last ထက္ position ႀကီးသြားမယ္ဆိုရင္ေတာ့ ဆက္ၿပီးေတာ့ ရွာေတာ့မွာ မဟုတ္ပါဘူး။

ပံုေလး ၂ ပံုကို နားလည္တယ္ဆိုရင္ေတာ့ ကၽြန္ေတာ္တို႔ေတြ code ကို စၿပီး ေရးႏိုင္ပါၿပီ။

k = [8,14,18,20,26,66,78] s = 18 found = False first = 0 last = len(k) - 1 while first <= last and not found: mid = (first + last)//2 mid_value = k[mid] if mid_value == s: found = True else: if s < mid_value : last = mid - 1 else: first = mid + 1 print(found)

first က last ထက္ ႀကီးသည့္ အဓိ အလုပ္လုပ္မယ္ ၊ ဒါမွမဟုတ္ ရွာေတြ႕ခဲ့ရင္ loop ထဲက ထြက္မယ္ ဆိုတာေၾကာင့္

while first <= last and not found:

ဆိုၿပီး ေရးထားတာပါ။ looping က firs က last ထက္ ငယ္ေနရင္ ဒါမွမဟုတ္ တူေနရင္ အလုပ္လုပ္မယ္။ ေနာက္ၿပီးေတာ့ found ကလည္း False ျဖစ္ေနရမယ္။ not found ဆိုသည့္ အဓိပၸာယ္ကေတာ့ not False ဆိုရင္ True ျဖစ္သြားသည့္ အတြက္ေၾကာင့္ condition မွာ ၂ ခု လံုး True ျဖစ္ေနသ၍ အလုပ္လုပ္မယ့္ သေဘာပါ။

mid = (first + last)//2

အဲဒီ code မွာ // ဆိုတာက ဒႆမ ကိန္း မယူဘူးလို႔ ဆိုတာပါ။ 3/2 ဆိုရင္ 1.5 ရပါတယ္။ 3//2 ဆိုရင္ေတာ့ 1 ပဲ ရပါတယ္။

ကၽြန္ေတာ္တို႔ code ကို ရွင္းသြားေအာင္ function ခြဲေရးပါမယ္။

def binary_search(array,item): first = 0 last = len(array) - 1 while first <= last: mid = (first + last)//2 mid_value = array[mid] if mid_value == item: return True else: if item < mid_value : last = mid - 1 else: first = mid + 1 return False print(binary_search([8,14,18,20,26,66,78],18)) print(binary_search([8,14,18,20,26,66,78],19))

ဒီလိုဆိုရင္ code ေလးက အေတာ္ေလးကို ရွင္းသြားပါၿပီ။ ဘယ္ အခန္းမွာ ရွာေတြ႕လဲဆိုသည့္ code အတြက္ကေတာ့ ေလ့က်င့္ခန္း အေနနဲ႔ ကိုယ္တိုင္ ေရးၾကည့္ပါ။

ကၽြန္ေတာ္ ထပ္ၿပီးေတာ့ recursive နဲ႔ ေရးၾကည့္ရေအာင္။

def binary_search(array,item): if len(array) == 0: return False mid = len(array)//2 mid_value = array[mid] if mid_value == item: return True else: if item < mid_value : return binary_search(array[:mid],item) else: return binary_search(array[mid+1:],item) print(binary_search([8,14,18,20,26,66,78],18)) print(binary_search([8,14,18,20,26,66,78],19))

first ႏွင့္ last အစား array ရဲ႕ size ကို တဝက္ဝက္ၿပီးေတာ့ mid ကို ယူထားတာကို ေတြ႕ႏိုင္ပါတယ္။ array[:mid] ႏွင့္ array[mid+1:] အေၾကာင္းကို ေတာ့ ကၽြန္ေတာ္ recursive အခန္းမွာ ေရးထားၿပီးသား ျဖစ္သည့္ အတြက္ နားလည္မယ္လို႔ ထင္ပါတယ္။ array ကို ထပ္ခါ ထပ္ခါ ပိုင္းၿပီး ရွာေနၿပီး ေနာက္ဆံုး array ကုန္သြားရင္ သို႔မဟုတ္ ရွာေတြ႕ခဲ့မွသာ recursive function ထဲကေန ထြက္မွာကို ေတြ႕ႏိုင္ပါတယ္။

results matching ""

    No results matching ""