First And Last Position Of An Element In A Sorted Array | FREE DSA Course in JAVA | Lecture 54
Вставка
- Опубліковано 22 січ 2023
- This question has been asked in the interview of Facebook, Google, and Microsoft and is a Leetcode problem number 34.
The question reads - Given an array of integer numbers sorted in ascending order, find the starting and ending position of a given target value.
if the target is not found in the array return [-1,-1].
You must write an algorithm with O(log n) runtime complexity.
Now a simple brute force approach will be to run a loop from the first index and return the index when the element is found first for a first position or starting position.
And, for the ending or last position run a loop from the last index.
But in this method, we will compromise with the time complexity given.
So one thing which is very clear is that we have to use the binary search algorithm for this program.
Let's see how a binary search approach with little changes can give the desired results as asked in this program.
Subscribe to our channel for regular updates on the dsa course and click on the bell icon to never miss an update from our dsa course.
Data Structures and Algorithms Free Course (Learn DSA Without Paise) Playlist - • Data Structures And Al...
For more information, fill this form: forms.gle/8eiUmM92Fx563Aen9
or call us at 8884881203
Facebook: / thetapacademy
Instagram: / tapacademy_online
Linkedin: / 73820805
Website: www.thetapacademy.com
#coding #dsa #dsacourse #java #javainterview #array #binarysearch
i gurantee nobody on youtube can explain better than him❤
You are such a genius made me understand very clearly when ever I have doubt on DSA I just immediately landed on your channel.
Sir, You made it this simple, directly entered to the brain, Thank you
You are very welcome. Do subscribe to the channel.
the way you explained this challenge...it is genius
SUCH A WONDERFUL EXPLAINATION BY YOU SIR. THANKS A LOT SIR. THE WAY YOU EXPLAIN EVERY PROBLEM IS JUST AWESOME😍
you guys make the best effort, you are great
Superb explaination sir 💥
very nice and simple explanation instead, easy to understand
Best explanation sir thank u so much❤️
Great lecture
best explanation sir
what an explaination wowwwwww
Given a list of sorted integers and a ‘key’, find and return the index of the first integer that is not less than the ‘key’. If no such integer exists, return -1. The complexity shall be O(logn). (Marks 10)
Example 1: {1, 2, 4, 5, 5, 6}, key = 2, returned index 2;
Example 2: {1, 2, 4, 5, 5, 6}, key = 3, returned index 3;
Example 3: {1, 2, 4, 5, 5, 6}, key = 5, returned index 4;
Example 4: {1, 2, 4, 5, 5, 6}, key = 7, returned index -1;
(Note: In the example, the indexing starts with 1 and not 0.)
Only PSEUDO-CODE is acceptable.
Sir kindly Solve this question
Super🤩
anybody clear me what if encounter if the first occurence at first index how should we approach we cant compare mid-1 because 0 is the last
Thank you so much😇
You're welcome 😊
sir,paste code in chat or give patreon link
String problem please
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res={-1,-1};
int beg=0,end=nums.length-1;
int mid=0;
while(begtarget)
end=mid-1;
else
beg=mid+1;
}
beg=0;
end=nums.length-1;
mid=0;
while(begtarget)
end=mid-1;
else
beg=mid+1;
}
return res;
}
}
THIS CODE IS NOT WORKING