कोडिंग इंटरव्यू: बाइनरी सर्च का उपयोग करके पहली और अंतिम स्थिति ज्ञात करना

समस्या और प्रासंगिक संदर्भ

गैर-घटते क्रम में सॉर्ट किया गया एक पूर्णांक ऐरे nums और एक पूर्णांक target दिया गया है, target के पहले और अंतिम इंडेक्स लौटाएं। जब यह अनुपस्थित हो तो [-1, -1] लौटाएं। ऐरे खाली हो सकता है और इसमें डुप्लिकेट्स हो सकते हैं, तथा फ़ंक्शन को इसे संशोधित (mutate) नहीं करना चाहिए। आवश्यक समय जटिलता (time complexity) O(log n) है जिसमें O(1) अतिरिक्त स्पेस शामिल है।

उदाहरण के लिए, nums = [1, 2, 2, 2, 3] और target = 2 पर [1, 3] मिलता है; target = 4 पर [-1, -1] मिलता है। एक लीनियर स्कैन से उत्तर प्राप्त किया जा सकता है, लेकिन इसका O(n) सबसे खराब स्थिति (worst case) आवश्यकता का उल्लंघन करता है।

यह प्रश्न सॉफ्टवेयर इंजीनियरिंग और एल्गोरिदम भूमिकाओं के कोडिंग राउंड के लिए उपयुक्त है। Amazon की वर्तमान SDE II इंटरव्यू गाइड सिंटैक्स की दृष्टि से सही, स्केलेबल, रोबस्ट और अच्छी तरह से टेस्ट किए गए कोड की अपेक्षा करती है, और LeetCode पर भी यही मूल समस्या मौजूद है। असली परीक्षा दो टेम्पलेट्स को याद रखना नहीं है। यह सर्च बाउंड्री को इतनी सटीकता से परिभाषित करना है कि लूप कंडीशन, इंटरवल अपडेट्स और रिटर्न वैल्यू सभी एक ही इनवेरिएंट का पालन करें।

इंटरव्यूअर क्या मूल्यांकन कर रहा है

पहला संकेत यह है कि उम्मीदवार यह पहचानता है या नहीं कि किसी भी एक उपस्थिति (occurrence) को खोजना पर्याप्त नहीं है। एक साधारण बाइनरी सर्च जो समानता पर रिटर्न करता है, वह सबसे बाईं या सबसे दाईं उपस्थिति की गारंटी नहीं देता है। एक उपस्थिति खोजने के बाद बाहर की ओर स्कैन करना अभी भी O(n) में बदल जाता है जब प्रत्येक तत्व टार्गेट के बराबर होता है।

दूसरा संकेत बाउंड्री सेमेन्टिक्स है। एक स्पष्ट विभाजन दो इंसर्शन पॉइंट्स की खोज करता है:

• lowerBound: पहली स्थिति जिसका मान target से बड़ा या उसके बराबर है।
• upperBound: पहली स्थिति जिसका मान target से कड़ाई से बड़ा (strictly greater) है।

Python के आधिकारिक bisect_left और bisect_right इन पार्टीशन परिभाषाओं का उपयोग करते हैं। एक बार दोनों बिंदु सही हो जाने पर, एक मौजूदा टार्गेट [lowerBound, upperBound - 1] को कवर करता है।

तीसरा संकेत लूप इनवेरिएंट है। हाफ-ओपन इंटरवल [left, right) के साथ, एक खाली ऐरे स्वाभाविक रूप से [0, 0) के रूप में शुरू होता है, और समाप्ति left === right होती है। क्लोज्ड-इंटरवल नियम को हाफ-ओपन इनिशियलाइज़ेशन के साथ मिलाना, जैसे कि right को nums.length पर सेट करना और बाद में nums[right] को पढ़ना, आउट-ऑफ-बाउंड्स एक्सेस या नॉन-टर्मिनेटिंग लूप का कारण बनता है।

अंत में, इंटरव्यूअर वेरिफिकेशन की तलाश करता है। एक मजबूत उत्तर में खाली ऐरे, एक तत्व, सभी डुप्लिकेट्स, न्यूनतम से नीचे का टार्गेट, अधिकतम से ऊपर का टार्गेट, दोनों सिरों पर टार्गेट्स और अनुपस्थित टार्गेट शामिल होते हैं। यह यह भी समझाता है कि target + 1 एक सामान्य अपर-बाउंड तकनीक क्यों नहीं है: यह एक असतत (discrete) संख्यात्मक उत्तराधिकारी पर निर्भर करता है, सबसे बड़े सुरक्षित पूर्णांक पर डोमेन से बाहर का मान बनाता है, और स्ट्रिंग्स या कस्टम कम्पेरेटर तक विस्तारित नहीं होता है।

उत्तर देने से पहले स्पष्टीकरण प्रश्न

• क्या ऐरे पहले से सॉर्ट किया गया है? यह प्रॉम्प्ट गैर-घटते क्रम की गारंटी देता है। मूल इंडेक्स को संरक्षित करते हुए

अनसॉर्टेड इनपुट को सॉर्ट करना डेटा मॉडल को बदल देता है और O(log n) की कुल सीमा को हटा देता है।

• क्या हम मूल या सॉर्ट किए गए इंडेक्स लौटाते हैं? वे यहाँ समान हैं क्योंकि इनपुट पहले से ही सॉर्ट किया गया है।
• अनुपस्थिति क्या दर्शाती है? इस प्रॉम्प्ट के लिए [-1, -1] की आवश्यकता होती है; इंसर्शन पॉइंट अपने आप में एक मैच नहीं होता है।
• क्या डुप्लिकेट मानों की अनुमति है? हाँ। डुप्लिकेट्स ही वह कारण हैं जिनकी वजह से बाउंड्री सर्च की आवश्यकता होती है।
• क्या ऐरे खाली हो सकता है? हाँ। हाफ-ओपन इम्प्लीमेंटेशन किसी भी एंडपॉइंट को पढ़े बिना इसे संभाल लेता है।
• संख्यात्मक डोमेन क्या है? मान JavaScript सेफ़ इंटीजर्स हैं। समाधान target + 1 की गणना नहीं करता है, इसलिए

यह सिर्फ बाउंड्री खोजने के लिए डोमेन से बाहर का सेंटिनल तैयार नहीं करता है।

• क्या बाइनरी सर्च को लागू किया जाना चाहिए? इस इंटरव्यू अभ्यास के लिए हाँ। प्रोडक्शन में, स्टैंडर्ड-लाइब्रेरी

फ़ंक्शन को प्राथमिकता दें जब इसका अनुबंध बिल्कुल मेल खाता हो।

• क्या इनपुट को संशोधित किया जा सकता है? नहीं, और किसी भी बाउंड्री सर्च को इसे संशोधित करने की आवश्यकता नहीं है।

30-सेकंड उत्तर फ्रेमवर्क

"मैं एक उपस्थिति खोजने और स्कैन करने के बजाय दो बाउंड्री सर्च चलाऊँगा। lowerBound हाफ-ओपन इंटरवल [left, right) में target से बड़े या बराबर पहले मान की खोज करता है; upperBound, target से कड़ाई से बड़े पहले मान को खोजता है। प्रत्येक पुनरावृत्ति (iteration) middle = left + floor((right - left) / 2) का उपयोग करती है। यदि मध्य बिंदु अभी भी टार्गेट के बाईं ओर है, तो left = middle + 1 सेट करें; अन्यथा right = middle के साथ मध्य बिंदु को बनाए रखें। मैं पहले जाँच करता हूँ कि लोअर बाउंड सीमा से बाहर है या टार्गेट के बराबर नहीं है। यदि यह मौजूद है, तो उत्तर [lower, upper - 1] है। दो सर्च O(1) अतिरिक्त स्पेस के साथ O(log n) ही रहते हैं।"

स्टेप-बाय-स्टेप डीप डाइव

स्टेप 1: "पहले और अंतिम" को दो विभाजन बिंदुओं (partition points) के रूप में फिर से लिखें।

nums = [1, 2, 2, 2, 3] और target = 2 के लिए:

lowerBound = 1  // first nums[i] >= 2
upperBound = 4  // first nums[i] > 2
answer = [1, 4 - 1] = [1, 3]

यह परिभाषा "बाईं ओर देखते रहें" और "दाईं ओर देखते रहें" की तुलना में सत्यापित करने में आसान है। टार्गेट अनुपस्थित होने पर भी इंसर्शन पॉइंट्स सार्थक रहते हैं। target = 4 के लिए, दोनों ऐरे की लंबाई 5 के बराबर हैं, लेकिन इसका मतलब यह नहीं है कि टार्गेट मौजूद है। एल्गोरिदम को अलग से nums[lower] === target की जाँच करनी चाहिए।

स्टेप 2: हाफ-ओपन इंटरवल इनवेरिएंट तय करें।

प्रत्येक lowerBound पुनरावृत्ति की शुरुआत में:

1. left से नीचे के प्रत्येक इंडेक्स में target से कड़ाई से कम मान होता है।
2. right पर या उससे ऊपर के प्रत्येक इंडेक्स में target से बड़ा या उसके बराबर मान होता है।
3. अनसुलझा उम्मीदवार इंटरवल [left, right) है।

प्रारंभ में, left = 0 और right = nums.length; दोनों बाहरी क्षेत्र खाली हैं, इसलिए इनवेरिएंट बना रहता है। यदि nums[middle] < target है, तो मध्य बिंदु और उसके बाईं ओर की कोई भी चीज़ उत्तर नहीं हो सकती, इसलिए left = middle + 1 सेट करें। अन्यथा, मध्य बिंदु पहली वैध स्थिति हो सकता है और इसे बनाए रखा जाना चाहिए, इसलिए right = middle सेट करें।

प्रत्येक पुनरावृत्ति इंटरवल को सख्ती से छोटा करती है। जब left === right होता है, तो कोई अनसुलझा तत्व नहीं बचता है। बाईं ओर की प्रत्येक चीज़ छोटी है और दाईं ओर की प्रत्येक चीज़ टार्गेट से बड़ी या बराबर है, इसलिए यह स्थिति लोअर बाउंड है।

upperBound एक अलग विभाजन के साथ समान संरचना का उपयोग करता है:

1. left से नीचे के प्रत्येक इंडेक्स में target से कम या उसके बराबर मान होता है।
2. right पर या उससे ऊपर के प्रत्येक इंडेक्स में target से कड़ाई से बड़ा मान होता है।

इसलिए यह left को तब आगे बढ़ाता है जब nums[middle] <= target हो और अन्यथा right को आगे बढ़ाता है।

स्टेप 3: दोनों बाउंड्री फ़ंक्शंस को लागू करें।

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

function upperBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (nums[middle] <= target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
}

केवल तुलना का अंतर है। दो स्पष्ट रूप से नामित फ़ंक्शंस को एक अपारदर्शी बूलियन स्विच वाले एक फ़ंक्शन की तुलना में इंटरव्यू में समझाना आसान है, और वे एक बार के उपयोग के लिए एक जटिल जेनेरिक एब्स्ट्रैक्शन बनाने से बचाते हैं।

मध्य बिंदु left + floor((right - left) / 2) है, इसलिए यह पहले दो बड़े इंडेक्स को नहीं जोड़ता है। JavaScript रनटाइम ऐरे सीमाएं इस प्रॉम्प्ट में इंडेक्स ओवरफ़्लो की संभावना को कम करती हैं, लेकिन यह एक्सप्रेशन निश्चित-चौड़ाई वाली पूर्णांक (fixed-width integer) भाषाओं में सुरक्षित रूप से काम करता है।

स्टेप 4: परिणामों को संयोजित करें और वास्तविक मैच सत्यापित करें।

function searchRange(nums: number[], target: number): [number, number] {
  const first = lowerBound(nums, target);

  if (first === nums.length || nums[first] !== target) {
    return [-1, -1];
  }

  return [first, upperBound(nums, target) - 1];
}

जाँच का क्रम मायने रखता है। nums[first] को पढ़ने से पहले first === nums.length का परीक्षण करें, ताकि ऐरे के बाद की स्थिति को एक तत्व के रूप में न माना जाए। एक बार जब first का मिलान होना ज्ञात हो जाता है, तो अपर बाउंड कम से कम first + 1 होता है, और एक घटाने पर अंतिम उपस्थिति प्राप्त होती है।

अपर बाउंड को lowerBound(nums, target + 1) - 1 से न बदलें। इस प्रॉम्प्ट के सेफ़-इंटीजर प्रतिबंध के तहत, यह अभी भी सही बाउंड्री लौटा सकता है, लेकिन Number.MAX_SAFE_INTEGER में एक जोड़ने से वह डोमेन छूट जाता है जिसमें सटीक पूर्णांक अंकगणित की गारंटी होती है। यदि इनपुट मनमाने JavaScript Numbers तक फैलता है, तो आसन्न पूर्णांक भी फ़्लोटिंग-पॉइंट परिशुद्धता के तहत समान हो सकते हैं। स्ट्रिंग्स, BigInt मानों और कस्टम कम्पेरेटर्स का कोई सार्वभौमिक "अगला मान" नहीं होता है। टार्गेट से कड़ाई से बड़े पहले मान को सीधे खोजना पूर्ण अनुबंध को व्यक्त करता है।

स्टेप 5: जटिलता (complexity) सिद्ध करें।

प्रत्येक लूप k लंबाई के एक उम्मीदवार इंटरवल को अधिकतम लगभग k / 2 तक कम करता है, इसलिए प्रत्येक बाउंड्री फ़ंक्शन O(log n) तुलनाएं करता है। दो सर्च अभी भी O(log n) हैं। एल्गोरिदम केवल इंडेक्स की एक स्थिर संख्या संग्रहीत करता है, O(1) अतिरिक्त स्पेस का उपयोग करता है, और ऐरे को संशोधित नहीं करता है।

किसी भी उपस्थिति को खोजना और बाहर की ओर स्कैन करना [2, 2, ..., 2] के लिए सभी n तत्वों पर जाता है, जिससे सबसे खराब स्थिति में O(n) प्राप्त होता है। एक प्रीकंप्यूटेड हैश टेबल बार-बार लुकअप को तेज़ बना सकती है, लेकिन इसके निर्माण में O(n) समय और स्पेस लगता है। यह केवल एक ही स्थिर इनपुट पर कई प्रश्नों के लिए उपयोगी है और दिए गए सॉर्ट किए गए क्रम के लाभ को अनदेखा करता है।

स्टेप 6: बाउंड्री मामलों और रैंडमाइज़्ड डिफरेंशियल टेस्ट्स के साथ मान्य करें।

कम से कम, इन्हें कवर करें:

फिर डुप्लिकेट्स के साथ सॉर्ट किए गए ऐरे जनरेट करें और परिणाम की तुलना लीनियर indexOf और lastIndexOf बेसलाइन से करें। लीनियर दृष्टिकोण लक्षित जटिलता को पूरा नहीं करता है, लेकिन यह एक उत्कृष्ट टेस्ट ओरेकल है। फिक्स्ड केसेस ज्ञात बाउंड्रीज की जाँच करते हैं, जबकि रैंडमाइज़्ड डिफरेंशियल टेस्ट्स विशेष डुप्लिकेट काउंट्स या एंडपॉइंट्स से जुड़ी त्रुटियों को उजागर करते हैं।

उच्च-गुणवत्ता वाला नमूना उत्तर

"ऐरे पहले से ही सॉर्ट किया गया है और आवश्यकता O(log n) है, इसलिए मैं एक टार्गेट ढूंढकर बाहर की ओर स्कैन नहीं करूँगा; पूरी तरह से डुप्लिकेट ऐरे लीनियर हो जाएगा। मैं उत्तर को दो इंसर्शन पॉइंट्स के साथ परिभाषित करता हूँ: टार्गेट से बड़ा या बराबर पहला मान, और टार्गेट से कड़ाई से बड़ा पहला मान।

दोनों सर्च हाफ-ओपन इंटरवल [left, right) का उपयोग करते हैं। बाईं बाउंड्री के लिए, इनवेरिएंट कहता है कि left से पहले सब कुछ टार्गेट से छोटा है और right से आगे सब कुछ इसके बराबर या बड़ा है। यदि मध्य बिंदु छोटा है, तो उत्तर दाईं ओर होना चाहिए, इसलिए मैं left = middle + 1 सेट करता हूँ। अन्यथा, मध्य बिंदु उत्तर हो सकता है, इसलिए मैं right = middle सेट करता हूँ। जब वे मिलते हैं, तो वह स्थिति लोअर बाउंड होती है। अपर बाउंड केवल शर्त को बदलता है: टार्गेट से कम या उसके बराबर मान left को स्थानांतरित करते हैं।

मैं पहले लोअर बाउंड की गणना करता हूँ। यदि यह ऐरे की लंबाई के बराबर है या इसमें टार्गेट नहीं है, तो मैं [-1, -1] लौटाता हूँ। अन्यथा, दायां एंडपॉइंट अपर बाउंड माइनस वन है। खाली इनपुट, अनुपस्थित टार्गेट, सभी डुप्लिकेट्स और किसी भी एंडपॉइंट पर मैच सभी समान लॉजिक का उपयोग करते हैं।

प्रत्येक पुनरावृत्ति इंटरवल को आधा कर देती है, इसलिए दो सर्च अभी भी O(log n) हैं और O(1) अतिरिक्त स्पेस का उपयोग करते हैं। मैं निश्चित बाउंड्री मामलों को सत्यापित करूँगा और फिर रैंडम सॉर्ट किए गए ऐरे की तुलना indexOf और lastIndexOf से करूँगा। मैं target + 1 का उपयोग नहीं करूँगा, क्योंकि यह बताए गए डोमेन के बाहर एक सेंटिनल बनाता है और अन्य ऑर्डर्ड डोमेन के लिए सामान्यीकृत नहीं होता है।"

सामान्य गलतियाँ

• किसी भी उपस्थिति को खोजना और बाहर की ओर स्कैन करना → सभी समान तत्वों वाला ऐरे O(n) बन जाता है → लोअर और अपर बाउंड्स को अलग-अलग बाइनरी-सर्च करें।
• समानता पर तुरंत रिटर्न करना → हिट सबसे बाईं या सबसे दाईं के बजाय मनमाना होता है → उस आधे हिस्से को बनाए रखें जिसमें अभी भी बाउंड्री हो सकती है।
• right को लंबाई पर इनिशियलाइज़ करना और nums[right] को पढ़ना → हाफ-ओपन एंडपॉइंट एक्सेस करने योग्य नहीं है → केवल middle पढ़ें और दोनों एंडपॉइंट मिलने पर समाप्त करें।
• left = middle के साथ अपडेट करना → दो-तत्वों वाला इंटरवल कभी छोटा नहीं हो सकता है → मध्य बिंदु को छोड़ते समय middle + 1 का उपयोग करें।
• अनुपस्थित टार्गेट के लिए इंसर्शन पॉइंट लौटाना → एक वैध इंसर्शन स्थिति मैच नहीं होती है → बाउंड्स और nums[first] !== target की जाँच करें।
• दाईं बाउंड्री के लिए target + 1 का उपयोग करना → यह डोमेन से बाहर या गैर-मौजूद उत्तराधिकारी पर निर्भर करता है → टार्गेट से कड़ाई से बड़ी पहली स्थिति को लागू करें।
• क्लोज्ड और हाफ-ओपन टेम्पलेट्स को मिलाना → इनिशियलाइज़ेशन, लूप कंडीशन और अपडेट्स में टकराव होता है → कोड से पहले इंटरवल सेमेन्टिक्स और इनवेरिएंट लिखें।
• केवल बीच में डुप्लिकेट्स का परीक्षण करना → खाली इनपुट, एंडपॉइंट्स और मिस्ड केसेस अभी भी विफल हो सकते हैं → एक बाउंड्री टेबल और रैंडमाइज़्ड डिफरेंशियल टेस्ट्स जोड़ें।
• यह दावा करना कि सॉर्ट-देन-सर्च अभी भी O(log n) है → सॉर्टिंग कुल लागत पर हावी होती है → सॉर्टेड-इनपुट गारंटी का उपयोग करें या पूरी जटिलता की पुनर्गणना करें।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: यदि आपको केवल यह परीक्षण करने की आवश्यकता है कि टार्गेट मौजूद है या नहीं, तो क्या आपको दो सर्च की आवश्यकता है?

नहीं। एक लोअर-बाउंड सर्च चलाएं और जांचें कि इसकी स्थिति सीमा में है और टार्गेट के बराबर है। वह O(log n) ही रहता है। यदि कोई मानक लाइब्रेरी ठीक यही अनुबंध प्रदान करती है, तो प्रोडक्शन कोड सीधे इसका उपयोग कर सकता है। दो सर्च केवल एक डुप्लिकेट रेंज के दोनों सिरों को प्राप्त करने के लिए आवश्यक हैं।

फॉलो-अप 2: आप उपस्थितियों की संख्या कैसे लौटाएंगे?

जब टार्गेट मौजूद होता है, तो गिनती upperBound - lowerBound होती है। जब यह अनुपस्थित होता है, तो दोनों इंसर्शन पॉइंट्स बराबर होते हैं, इसलिए अंतर भी शून्य होता है। इसलिए केवल-गिनती वाले फ़ंक्शन को ऐरे तत्व को पढ़ने की भी आवश्यकता नहीं होती है। यह सूत्र इसलिए काम करता है क्योंकि दोनों बाउंड्रीज के बीच का प्रत्येक तत्व टार्गेट के बराबर होता है।

फॉलो-अप 3: यदि ऐरे अवरोही (descending) क्रम में सॉर्ट किया गया है तो क्या बदलता है?

इनवेरिएंट और तुलनाओं को उलट दें। एक अवरोही लोअर बाउंड का अर्थ टार्गेट से कम या उसके बराबर पहला मान हो सकता है, और दूसरी बाउंड्री इससे कड़ाई से कम पहला मान होती है। मूल तुलनाओं को बनाए रखते हुए केवल अंतिम व्याख्या को न उलटें। पहले पार्टीशन प्रेडिकेट को परिभाषित करें, फिर इसके सत्य मान (truth value) से इंटरवल को अपडेट करें।

फॉलो-अप 4: क्या होगा यदि तत्व ऑब्जेक्ट्स हैं और सर्च एक फ़ील्ड का उपयोग करता है?

एक सॉर्ट की गई तुलना कुंजी खोजें, जैसे कि createdAt। यदि बार-बार किए जाने वाले प्रश्नों में कुंजी निष्कर्षण महंगा है, तो एक प्रीकंप्यूटेड की-ऐरे रखें; Python दस्तावेज़ भी महंगी कुंजियों को कैश या प्रीकंप्यूट करने की सलाह देता है। ऑब्जेक्ट अनुक्रम को सर्च के दौरान संशोधित नहीं किया जाना चाहिए, अन्यथा सॉर्ट किया गया इनवेरिएंट मान्य नहीं रहता है।

फॉलो-अप 5: क्या होगा यदि डेटा मेमोरी के बजाय ऑर्डर्ड इंडेक्स वाले डेटाबेस में है?

एप्लिकेशन बाइनरी सर्च को कई रिमोट प्रश्नों में न बदलें। डेटाबेस इंडेक्स को रेंज का पता लगाने दें, जैसे टार्गेट के बराबर न्यूनतम और अधिकतम स्थिर सॉर्ट कुंजियाँ या एक इंडेक्स रेंज स्कैन। प्रति बाइनरी सर्च पुनरावृत्ति एक नेटवर्क राउंड ट्रिप O(log n) तुलनाओं को बार-बार उच्च-विलंबता (high-latency) वाले कॉल्स में बदल देता है और समवर्ती (concurrent) राइट्स के दौरान विभिन्न स्नैपशॉट देख सकता है।

फॉलो-अप 6: यह टेम्पलेट "न्यूनतम व्यवहार्य उत्तर (minimum feasible answer)" समस्याओं तक कैसे विस्तारित होता है?

एक मोनोटोनिक प्रेडिकेट को परिभाषित करें, जैसे कि x से नीचे की प्रत्येक क्षमता अव्यवहार्य है और किसी बिंदु के बाद की प्रत्येक क्षमता व्यवहार्य है। फिर एक अंतर्निहित उत्तर स्पेस पर पहले ट्रू प्रेडिकेट को लोअर-बाउंड करें, जहाँ nums[middle] < target को !feasible(middle) से बदल दिया जाए। प्रेडिकेट को केवल एक बार फॉल्स से ट्रू में परिवर्तित होने के लिए सिद्ध किया जाना चाहिए; यदि सत्य मान वैकल्पिक रूप से बदलते हैं, तो बाइनरी सर्च का कोई शुद्धता आधार नहीं होता है।