Xét mảng sắp xếp tăng dần. Mảng bị xoay tại pivot không biết trước. Ví dụ [0,0,1,2,2,5,6] có thể thành [2,5,6,0,0,1,2]. Ta có giá trị target cần tìm. Nếu tìm thấy trả về true, ngược lại false. Nếu mảng [2,5,6,0,0,1,2], target 0, kết quả true.
Các bước −
- low := 0, high := độ dài mảng
- khi low < high
- mid := low + (high - low)/2
- nếu nums[mid] = target, trả về true
- nếu nums[low] = nums[mid] và nums[high-1] = nums[mid], thì
- tăng low 1, giảm high 1, continue
- nếu nums[low] <= nums[mid], thì
- nếu target >= nums[low] và target < nums[mid], high := mid, ngược lại low := mid + 1
- ngược lại
- nếu target <= nums[high-1] và target > nums[mid], low := mid + 1, ngược lại high := mid
- trả về false
Xem triển khai sau −
Ví dụ
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))
Đầu vào
[2,5,6,0,0,1,2] 0
Kết quả
True