Advertisement
Iam_Sandeep

Find target in Rotated Sorted Array Binary Search

Jul 2nd, 2022 (edited)
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.82 KB | None | 0 0
  1. #If there are no duplicates.There is second part which have duplicates. Go down and check
  2. class Solution:
  3.     #Always the inflection point exists in unsorted part of array.
  4.     #Either left half or right half of inflecton point will be in increasing order surely.
  5.     def search(self, arr: List[int], target: int) -> int:
  6.         n=len(arr)
  7.         l,r=0,n-1
  8.         while l<=r:
  9.             m=(l+r)//2
  10.             if arr[m]==target:#target condition
  11.                 return m
  12.             elif arr[l]<=arr[m]:#Left is sorted
  13.                 if arr[l]<=target<=arr[m]: #check if available in sorted part
  14.                     r=m-1
  15.                 else:#If not available in sorted part move l to right side
  16.                     l=m+1
  17.             else:#Right is sorted
  18.                 if arr[m]<=target<=arr[r]:#check if available in sorted par
  19.                     l=m+1
  20.                 else:#If not available in sorted part move r to left side
  21.                     r=m-1
  22.                
  23.         return -1
  24. #If there are  duplicates
  25. class Solution:
  26.     def search(self, nums: List[int], target: int) -> bool:
  27.         n=len(nums)
  28.         l,r=0,n-1
  29.         while l<=r:
  30.             m=(l+r)//2
  31.             if nums[m]==target:
  32.                 return True
  33.             elif nums[l]==nums[m]==nums[r]:#extra condition or else we cant judge where to go
  34.                 l+=1
  35.                 r-=1
  36.             elif nums[l]<=nums[m]:
  37.                 if nums[l]<=target<nums[m]:
  38.                     r=m-1
  39.                 else:
  40.                     l=m+1
  41.             else:
  42.                 if nums[m]<target<=nums[r]:
  43.                     l=m+1
  44.                 else:
  45.                     r=m-1
  46.         return False
  47. e.g.[1,0,1,1,1]
  48. search=0
  49. 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