Hãy xem xét chúng ta có một mảng được sắp xếp theo thứ tự tăng dần. Điều đó được xoay ở một số trục mà chúng ta chưa biết trước. Ví dụ:nếu mảng giống như [0,0,1,2,2,5,6], thì mảng này có thể trở thành [2,5,6,0,0,1,2]. Chúng tôi có một giá trị mục tiêu để tìm kiếm. Nếu điều đó được tìm thấy trong mảng, thì trả về true, nếu không thì trả về false. Vì vậy, nếu mảng giống như [2,5,6,0,0,1,2] và mục tiêu là 0, thì kết quả đầu ra sẽ là 0
Hãy để chúng tôi xem các bước -
-
thấp:=0 và cao:=kích thước của mảng
-
trong khi thấp
-
giữa:=low + (cao - thấp) / 2
-
nếu nums [mid] =target, thì trả về true
-
nếu nums [low] =nums [mid] và nums [high - 1] =nums [mid] thì
-
tăng mức thấp 1 và giảm mức cao 1 và tiếp tục cho lần lặp tiếp theo
-
-
nếu nums [low] <=nums [mid] thì
-
nếu target> =nums [low] và target
-
-
Nếu không
-
nếu target <=nums [high - 1] và target> nums [mid] thì low:=mid + 1, ngược lại high:=mid
-
-
trả về false
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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
Đầu vào
[2,5,6,0,0,1,2] 0
Đầu ra
true