Created
June 19, 2022 10:25
-
-
Save satyajeetkrjha/66041fcd1f7f5418bd93a48ee5c18c0b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| if( nums[mid] == target && (mid == 0 or nums[mid-1]!=target)) | |
| in this piece of code ,if mid turns out to 0 then nums[mid-1] is not evaluated and this will not lead to run time error . | |
| this is called short circuit evaluation . | |
| Similary | |
| if(nums[mid] == target && (mid +1== nums.size() or nums[mid+1]!=target)) | |
| the code nums[mid+1] is not evaluated if mid+1 is already equal to nums.size() | |
| */ | |
| class Solution { | |
| public: | |
| vector<int> searchRange(vector<int>& nums, int target) { | |
| if(nums.size() == 0 ){ | |
| return {-1,-1}; | |
| } | |
| int left =0 ; | |
| int right = nums.size()-1; | |
| int start = -1 ; | |
| while(left <=right){ | |
| int mid = (left+right)/2; | |
| if( nums[mid] == target && (mid == 0 or nums[mid-1]!=target)){ | |
| start= mid; | |
| break; | |
| } | |
| else if(nums[mid]>=target){ | |
| right = mid-1; | |
| } | |
| else{ | |
| left = mid+1; | |
| } | |
| } | |
| int last = -1 ; | |
| left =0; | |
| right = nums.size() -1; | |
| while(left <= right){ | |
| int mid =(left+right)/2 ; | |
| if(nums[mid] == target && (mid +1== nums.size() or nums[mid+1]!=target)){ | |
| last = mid ; | |
| break; | |
| } | |
| else if(nums[mid] <= target){ | |
| left = mid+1; | |
| } | |
| else { | |
| right = mid -1 ; | |
| } | |
| } | |
| return {start,last}; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment