พิจารณาว่าเรามีอาร์เรย์ที่เรียงลำดับจากน้อยไปมาก นั่นคือการหมุนที่จุดหมุนที่เราไม่รู้จักล่วงหน้า ตัวอย่างเช่น ถ้าอาร์เรย์เป็นเหมือน [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
-
ถ้า nums[mid] =เป้าหมาย คืนค่า true
-
ถ้า nums[low] =nums[mid] และ nums[high - 1] =nums[mid] แล้ว
-
เพิ่มขึ้นต่ำ 1 และลดลงสูง 1 และดำเนินการซ้ำต่อไป
-
-
ถ้า nums[low] <=nums[mid] แล้ว
-
ถ้าเป้าหมาย>=nums[ต่ำ] และเป้าหมาย
-
-
มิฉะนั้น
-
ถ้าเป้าหมาย <=nums[สูง - 1] และเป้าหมาย> nums[กลาง] แล้วต่ำ :=กลาง + 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
