Xét một mảng được sắp xếp tăng dần. Mảng này bị xoay tại một pivot không biết trước. Ví dụ, mảng [0,0,1,2,2,5,6] có thể trở thành [2,5,6,0,0,1,2]. Chúng ta có một giá trị mục tiêu để tìm. Nếu tìm thấy trong mảng, trả về true, ngược lại false. Ví dụ, mảng [2,5,6,0,0,1,2], target = 0, kết quả true.
Các bước thực hiện:
- low := 0 và high := kích thước mảng
- while low < high
- mid := low + (high - low)/2
- nếu nums[mid] = target, return true
- nếu nums[low] = nums[mid] và nums[high - 1] = nums[mid], thì
- tăng low 1, giảm high 1, tiếp tục vòng lặp tiếp theo
- nếu nums[low] <= nums[mid], thì
- nếu target >= nums[low] và target < nums[mid], thì high := mid, ngược lại low := mid + 1
- Ngược lại
- nếu target <= nums[high - 1] và target > nums[mid], thì low := mid + 1, ngược lại high := mid
- return false
Ví dụ
Hãy xem 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
Input
[2,5,6,0,0,1,2] 0
Output
true