Binary search ले क्रमबद्ध ऐरेमा लक्ष्य खोज्छ र बारम्बार सर्च दायरा आधा गरेर फेला पार्छ। प्रत्येक तुलनाले बाकी आधा तत्वहरू हटाई दिन्छ, जसले O(log n) समय दिन्छ।
विचार
मध्य तत्वलाई हेर्नुहोस्। यदि यो लक्ष्यसँग बराबर छ भने, समाप्त। यदि लक्ष्य सानो छ भने, बायाँ आधा सर्च गर्नुहोस्; यदि ठूलो छ भने, दायाँ आधा सर्च गर्नुहोस्। जबसम्म फेला नपरे वा दायरा खाली नहोए सम्म दोहोर्याउनुहोस्।
उदाहरण
():
lo, hi = , (arr) -
lo <= hi:
mid = (lo + hi) //
arr[mid] == target:
mid
arr[mid] < target:
lo = mid +
:
hi = mid -
-
binary_search([, , , , ], )
