विचार करें कि हमारे पास आरोही क्रम में क्रमबद्ध एक सरणी है। यह हमारे लिए पहले से अज्ञात किसी धुरी पर घुमाया जाता है। उदाहरण के लिए, यदि सरणी [0,0,1,2,2,5,6] की तरह है, तो यह [2,5,6,0,0,1,2] बन सकती है। हमारे पास खोज करने के लिए एक लक्षित मूल्य है। यदि वह सरणी में पाया जाता है, तो सही लौटें, अन्यथा झूठी वापसी करें। तो अगर सरणी [2,5,6,0,0,1,2] की तरह है, और लक्ष्य 0 है, तो आउटपुट 0
होगाआइए चरणों को देखें -
-
निम्न:=0 और उच्च:=सरणी का आकार
-
जबकि कम <उच्च
-
मध्य :=निम्न + (उच्च-निम्न)/2
-
अगर अंक [मध्य] =लक्ष्य, तो सही लौटें
-
यदि अंक [निम्न] =अंक [मध्य] और अंक [उच्च -1] =अंक [मध्य], तो
-
1 से कम बढ़ाएं और 1 से उच्च घटाएं, और अगले पुनरावृत्ति के लिए जारी रखें
-
-
अगर अंक [निम्न] <=अंक [मध्य], तो
-
यदि लक्ष्य>=अंक [निम्न] और लक्ष्य <अंक [मध्य], तो उच्च:=मध्य, अन्यथा निम्न:=मध्य + 1
-
-
अन्यथा
-
यदि लक्ष्य <=अंक [उच्च -1] और लक्ष्य> अंक [मध्य], तो निम्न:=मध्य + 1, अन्यथा उच्च:=मध्य
-
-
झूठी वापसी
-
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ low = 0 high = len(nums) while low<high: mid = low + (high-low)//2 print(mid) if nums[mid] == target: return True if nums[low] == nums[mid] and nums[high-1] == nums[mid]: low +=1 high -=1 continue if nums[low]<=nums[mid]: if target >=nums[low] and target <nums[mid]: high = mid else: low = mid+1 else: if target<=nums[high-1] and target>nums[mid]: low = mid+1 else: high = mid return False
इनपुट
[2,5,6,0,0,1,2] 0
आउटपुट
true