Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #If there are no duplicates.There is second part which have duplicates. Go down and check
- class Solution:
- #Always the inflection point exists in unsorted part of array.
- #Either left half or right half of inflecton point will be in increasing order surely.
- def search(self, arr: List[int], target: int) -> int:
- n=len(arr)
- l,r=0,n-1
- while l<=r:
- m=(l+r)//2
- if arr[m]==target:#target condition
- return m
- elif arr[l]<=arr[m]:#Left is sorted
- if arr[l]<=target<=arr[m]: #check if available in sorted part
- r=m-1
- else:#If not available in sorted part move l to right side
- l=m+1
- else:#Right is sorted
- if arr[m]<=target<=arr[r]:#check if available in sorted par
- l=m+1
- else:#If not available in sorted part move r to left side
- r=m-1
- return -1
- #If there are duplicates
- class Solution:
- def search(self, nums: List[int], target: int) -> bool:
- n=len(nums)
- l,r=0,n-1
- while l<=r:
- m=(l+r)//2
- if nums[m]==target:
- return True
- elif nums[l]==nums[m]==nums[r]:#extra condition or else we cant judge where to go
- l+=1
- r-=1
- elif nums[l]<=nums[m]:
- if nums[l]<=target<nums[m]:
- r=m-1
- else:
- l=m+1
- else:
- if nums[m]<target<=nums[r]:
- l=m+1
- else:
- r=m-1
- return False
- e.g.[1,0,1,1,1]
- search=0
- If we dont use that extra condition we cant judge which side to go sometimes when a[l] and a[m] are equal
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement