Search in Rotated Sorted Array (LeetCode 33) | FREE DSA Course in JAVA | Lecture 55
10.1 هزار بار بازدید -
2 سال پیش
-
This question has been asked
This question has been asked in dream companies like Google, and Amazon and is a Leetcode problem number 33.
The question reads - There is an integer array nums sorted in ascending order (with distinct values).
Before being passed to your function, nums may be rotated at an unknown pivot index k. For example, (0,1,2,4,5,6,7) might be turned at pivot index 3 and become (4,5,6,7,0,1,2). You have to find the index of a given target value. if the target value is not present return -1.
You must write an algorithm with O(log n) runtime complexity.
Now if a search has to be done on an array in log n complexity, the only way you can do it, is by making a Binary search.
But the trick is that it is not entirely sorted after the rotation and hence we need to follow a different approach.
Let's see how we can solve this search in the rotated array problem in java.
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 Algorithms Full C...
For more information, fill this form: https://forms.gle/8eiUmM92Fx563Aen9
or call us at 8884881203
Facebook: Facebook: thetapacademy
Instagram:Instagram: tapacademy_online
Linkedin: LinkedIn: 73820805
Website: https://www.thetapacademy.com
The question reads - There is an integer array nums sorted in ascending order (with distinct values).
Before being passed to your function, nums may be rotated at an unknown pivot index k. For example, (0,1,2,4,5,6,7) might be turned at pivot index 3 and become (4,5,6,7,0,1,2). You have to find the index of a given target value. if the target value is not present return -1.
You must write an algorithm with O(log n) runtime complexity.
Now if a search has to be done on an array in log n complexity, the only way you can do it, is by making a Binary search.
But the trick is that it is not entirely sorted after the rotation and hence we need to follow a different approach.
Let's see how we can solve this search in the rotated array problem in java.
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 Algorithms Full C...
For more information, fill this form: https://forms.gle/8eiUmM92Fx563Aen9
or call us at 8884881203
Facebook: Facebook: thetapacademy
Instagram:Instagram: tapacademy_online
Linkedin: LinkedIn: 73820805
Website: https://www.thetapacademy.com
2 سال پیش
در تاریخ 1401/11/04 منتشر شده
است.
10,131
بـار بازدید شده