พิจารณาว่าเรามีอาร์เรย์ที่เรียงลำดับจากน้อยไปมาก นั่นคือการหมุนที่จุดหมุนที่เราไม่รู้จักล่วงหน้า ตัวอย่างเช่น ถ้าอาร์เรย์เป็นเหมือน [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[ต่ำ] <=nums[กลาง] แล้ว
- ถ้าเป้าหมาย>=nums[ต่ำ] และเป้าหมาย &miinus; nums[mid], then high :=mid, มิฉะนั้น low :=mid + 1
- มิฉะนั้น
- ถ้าเป้าหมาย <=nums[สูง - 1] และเป้าหมาย> nums[กลาง] แล้วต่ำ :=กลาง + 1 มิฉะนั้นสูง :=กลาง
- คืนค่าเท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def search(self, nums, target): low = 0 high = len(nums) while low<high: mid = low + (high-low)//2 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 ob1 = Solution() print(ob1.search([2,5,6,0,0,1,2], 0))
อินพุต
[2,5,6,0,0,1,2] 0
ผลลัพธ์
True
