मान लीजिए हमारे पास n अद्वितीय संख्याओं की एक सरणी A है, ये n तत्व सरणी में आरोही क्रम में मौजूद हैं, लेकिन एक लापता तत्व है। हमें लापता तत्व ढूंढना है।
तो, यदि इनपुट A = [1, 2, 3, 4, 5, 6, 7, 9] की तरह है, तो आउटपुट 8 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
n := A का आकार
left := 0
right := n - 1
mid := 0
जब right > left, करें
mid := left + (right - left) / 2
यदि A[mid] - mid, A[0] के समान है, तो
यदि A[mid + 1] - A[mid] > 1, तो
A[mid] + 1 वापस करें
अन्यथा,
left := mid + 1
अन्यथा,
यदि A[mid] - A[mid - 1] > 1, तो
A[mid] - 1 वापस करें
अन्यथा,
right := mid - 1
-1 वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def search_missing_item(A): n = len(A) left, right = 0, n - 1 mid = 0 while (right > left): mid = left + (right - left) // 2 if (A[mid] - mid == A[0]): if (A[mid + 1] - A[mid] > 1): return A[mid] + 1 else: left = mid + 1 else: if (A[mid] - A[mid - 1] > 1): return A[mid] - 1 else: right = mid - 1 return -1 A = [1, 2, 3, 4, 5, 6, 7, 9] print(search_missing_item(A))
इनपुट
[1, 2, 3, 4, 5, 6, 7, 9]
आउटपुट
8
