బైనరీ సర్చ్ ఎలా పనిచేస్తుంది, మరియు దానికి ఏమి అవసరం?

Question

Accepted Answer

**బైనరీ సర్చ్** సార్టు చేయబడిన శ్రేణిలో సర్చ్ పరిధిని పదేపదే సగానికి తగ్గించడం ద్వారా లక్ష్యాన్ని కనుగొంటుంది. ప్రతిটి పోలిక మిగిలిన మూలకాలలో సగం తొలగిస్తుంది, ఇది **O(log n)** సమయం ఇస్తుంది. ## ఆలోచన మధ్య మూలకను చూడండి. ఇది లక్ష్యానికి సమానమైతే, పూర్తి. లక్ష్యం చిన్నది అయితే, ఎడమ సగం సర్చ్ చేయండి; పెద్దది అయితే, కుడి సగం సర్చ్ చేయండి. కనుగొనే వరకు లేదా పరిధి ఖాళీ వరకు పునరావృత్తి చేయండి. ## ఉదాహరణ ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## ట్రేస్ ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## సంక్లిష్టత - **సమయం:** O(log n). **స్థలం:** O(1) పునరావృత్తి. ## విషయిలు **ఇన్‌పుట్ సార్టు చేయబడి ఉండాలి** — లేకపోతే ఫలితాలు అర్థరహితం. `lo`/`hi` లో ఆఫ్-బై-ওয়ან్ బగ్‌లు మరియు కొన్ని భాషలలో పూర్ణాంక ఓవర్‌ఫ్లో గురించి జాగ్రత్తగా ఉండండి (`lo + (hi-lo)//2` ఉపయోగించండి). ## ఇది ఎందుకు ముఖ్యమైనది సర్చ్ స్పేస్ సగానికి తగ్గించడం ఒక మిలియన్-ఎలిమెంట్ సర్చ్‌ను ~20 పోలికలుగా మారుస్తుంది. పాలించండి-కన్ కర్ విధానం దాని వెనుక చెలరేవు చేస్తుంది, డేటాబేసులు మరియు లెక్కలేనన్ని ఇంటర్‌వ్యూ సమస్యలలో చెరిపిన చెట్లలో. దాని ఒక కఠినమైన అవసరాన్ని తెలుసుకోవడం — సార్టు చేయబడిన ఇన్‌పుట్ — మీ నుండి ఒక సాధారణ సూక్ష్మ బగ్‌ను దూరంగా ఉంచుతుంది.