బైనరీ శోధన అల్గోరిథం అనేది క్రమబద్ధీకరించబడిన శ్రేణిలో నిర్దిష్ట విలువను కనుగొనడానికి సమర్థవంతమైన పద్ధతి. ఈ విధానం శ్రేణిని చిన్న భాగాలుగా విభజిస్తుంది మరియు శోధన పరిధి మధ్య స్థానంలో ఉన్న విలువను లక్ష్య విలువతో నిరంతరం పోలుస్తుంది. విలువలు సరిపోలితే, కావలసిన విలువ కనుగొనబడుతుంది; లేకపోతే, అల్గోరిథం శోధన పరిధిని తగ్గించడాన్ని కొనసాగిస్తుంది మరియు విలువ కనుగొనబడే వరకు లేదా పరిశీలించడానికి మరిన్ని అంశాలు మిగిలిపోయే వరకు ప్రక్రియను పునరావృతం చేస్తుంది.
దశలు:
- శోధన పరిధిని ప్రారంభించండి: శ్రేణి యొక్క మొదటి స్థానం
leftనుండి చివరి స్థానం వరకు శోధన పరిధిని ఎంచుకోవడం ద్వారా ప్రారంభించండి.right - మధ్య బిందువును కనుగొనండి: మధ్య బిందువును
leftమరియు కుడి స్థానాలను సగటుతో లెక్కించండి; ఇది శోధన పరిధి మధ్య బిందువు. - విలువలను సరిపోల్చండి: మధ్య బిందువు వద్ద ఉన్న విలువను లక్ష్య విలువతో సరిపోల్చండి.
- హ్యాండిల్ పోలిక ఫలితం: మధ్య బిందువు వద్ద ఉన్న విలువ లక్ష్య విలువతో సరిపోలితే, ఈ స్థానాన్ని తిరిగి ఇవ్వండి. మధ్య బిందువు వద్ద ఉన్న విలువ లక్ష్య విలువ కంటే తక్కువగా ఉంటే, కుడి సగాన్ని శోధించడానికి ఎడమ స్థానాన్ని మధ్య + 1కి అప్‌డేట్ చేయండి. మధ్య బిందువు వద్ద ఉన్న విలువ లక్ష్య విలువ కంటే ఎక్కువగా ఉంటే, ఎడమ అర్ధ భాగాన్ని శోధించడానికి కుడి స్థానాన్ని మధ్య- 1కి అప్‌డేట్ చేయండి.
- పునరావృతం: విలువ కనుగొనబడే వరకు 2 నుండి 4 దశలను పునరావృతం చేయండి లేదా తనిఖీ చేయడానికి మరిన్ని అంశాలు లేవు
left > right.
ప్రయోజనాలు మరియు అప్రయోజనాలు
ప్రయోజనాలు:
- సమర్థవంతమైన పనితీరు: అల్గోరిథం యొక్క సమయ సంక్లిష్టత O(log n), ఇది పెద్ద డేటాసెట్‌లను నిర్వహించడానికి అత్యంత ప్రభావవంతంగా ఉంటుంది.
- పెద్ద డేటాసెట్‌ల కోసం ప్రభావవంతంగా ఉంటుంది: పెద్ద డేటాసెట్‌ల కోసం త్వరగా పరిశీలించడానికి మూలకాల సంఖ్యను తగ్గించడంలో బైనరీ శోధన ప్రభావవంతంగా ఉంటుంది.
ప్రతికూలతలు:
- క్రమబద్ధీకరించబడిన శ్రేణులకు మాత్రమే వర్తిస్తుంది: అల్గోరిథం క్రమబద్ధీకరించబడిన శ్రేణులపై మాత్రమే పని చేస్తుంది.
- వేరియబుల్ దశల సంఖ్య: విలువను కనుగొనడానికి అవసరమైన దశల సంఖ్య శ్రేణిలో దాని స్థానంపై ఆధారపడి ఉంటుంది మరియు చివరల దగ్గర విలువల కోసం ఇది చాలా దశలను తీసుకోవచ్చు.
ఉదాహరణ: PHPలో క్రమబద్ధీకరించబడిన శ్రేణిలో 12 విలువను కనుగొనడం కోసం బైనరీ శోధన
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr)- 1;
while($left <= $right) {
$mid = floor(($left + $right) / 2);
if($arr[$mid] == $target) {
return $mid; // Return the position of the value
} elseif($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid- 1;
}
}
return -1; // Value not found
}
$array = [2, 5, 8, 12, 15, 20, 30];
$targetValue = 12;
$result = binarySearch($array, $targetValue);
if($result != -1) {
echo "Value $targetValue found at position $result.";
} else {
echo "Value $targetValue not found in the array.";
}
ఉదాహరణ యొక్క వివరణ
- మేము శ్రేణి యొక్క మొదటి స్థానం నుండి
left = 0చివరి స్థానం వరకు ప్రారంభ శోధన పరిధితో ప్రారంభిస్తాము.right = 6 - మేము ఎడమ మరియు కుడి స్థానాలను సగటున మధ్య బిందువు(మధ్య) లెక్కిస్తాము;
mid = 3. మధ్యలో విలువ 12. - మేము) వద్ద ఉన్న విలువను
mid(12లక్ష్య విలువ(12)తో సరిపోల్చాము మరియు సరిపోలికను కనుగొంటాము, కాబట్టి మేము స్థానం 3ని తిరిగి ఇస్తాము. - అల్గోరిథం ముగుస్తుంది మరియు మేము "స్థానం 3 వద్ద కనుగొనబడిన విలువ 12" ఫలితాన్ని అవుట్‌పుట్ చేస్తాము.