To make sure your calendar, event reminders, and other features are always
correct, please tell us your time zone (and other details) using the
drop-down menus below:
Set Date/Time format:
In 12 Hour format the hours will be displayed as 1 through 12 with “a.m.” and “p.m.”
displayed after the time (ex. 1:00p.m.). In 24 hour format the hours will be displayed as 00 through 23 (ex. 13:00).
You can always change your time zone by going to your Account Settings.
Use the dropdown menu to view the events in another time zone. The primary time zone will be displayed in parentheses.
Use the dropdown menu to view the events in another time zone. The primary time zone will be displayed in parentheses.
Visiting Rany Milton(username: itsrandy)
Tag
Please wait...
Select a Color
Manage Applications
Check the items that you want displayed. Uncheck all to hide the section.
Calendars
Files
Addresses
To Dos
Discussions
Photos
Bookmarks
The “Switch Navigator” button will no longer be available after February 14, 2017.
Please learn more about how to use the new Navigator by clicking this link.
01.DS.02.02. Search a Rotated Array.html -- 1.9 meg
Search a Rotated Array - Coderust: Hacking the Coding Interview
We’re given a sorted integer array, nums and an integer value, target. The array is rotated by some arbitrary number. Search the target in this array. If the target does not exist then return -1.
The solution is essentially a binary search but with some modifications. When we look at the array in the example, you may notice that at least one-half of the array is always sorted. We can use this property to our advantage. If the target lies within the sorted half of the array, our problem is a basic binary search. Otherwise, discard the sorted half and keep examining the unsorted half. Since we partition the array in half at each step, this gives us O(log n)O(log \space n)O(logn) runtime complexity.
Let’s assume we have the same array we saw above (rotated 6 times) and our target is 200200200.
Created with Fabric.js 3.6.6This is our initial setup.target: 20001234567891011121314151617181917618819920021022211020475963758899107120133155162
1 of 14
Created with Fabric.js 3.6.6Let's initialize our low, mid, and high pointers.target: 200low01234567891011121314151617181917618819920021022211020475963758899107120133155162midhigh
1 of 14
Created with Fabric.js 3.6.6We compare the values of the low, mid, and high pointers. Since array[mid] < array[high], we know that the section from mid to high is sorted.target: 200low01234567891011121314151617181917618819920021022211020475963758899107120133155162midhigh
1 of 14
Created with Fabric.js 3.6.6We also check if the target value lies in this section's range (47 - 162) and since it doesn't, we will continue our search in the section between the low and mid pointers.target: 200low01234567891011121314151617181917618819920021022211020475963758899107120133155162midhigh
1 of 14
Created with Fabric.js 3.6.6We update the high pointer to mid -1. We can also discard the section to the right of the mid pointer.Once high pointer is updated, we can also update our mid pointer.target: 200low01234567891011121314151617181917618819920021022211020475963758899107120133155162midhigh
1 of 14
C++
Java
Python
JS
Ruby
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>
usingnamespace std;
int BinarySearchRotated(vector<int>& nums,int target){
int start =0;
int mid =0;
int end = nums.size()-1;
if(start > end)return-1;
while(start <= end){
// Finding the mid using floor division
mid = start +(end - start)/2;
// Target value is present at the middle of the numsay
if(nums[mid]== target)return mid;
// start to mid is sorted
if(nums[start]<= nums[mid]){
if(nums[start]<= target && target < nums[mid]){
end = mid -1;
}
else{
start = mid +1;
}
}
// mid to end is sorted
else{
#
#include <iostream>
#include <vector>
using namespace std;
int BinarySearchRotated(vector<int>& nums, int target) {
int start = 0;
int mid = 0;
int end = nums.size() - 1;
In this solution, we will use the recursive binary search approach to locate the target. Each recursive call considers half of the array passed to it.
C++
Java
Python
JS
Ruby
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>
usingnamespace std;
int BinarySearch(vector<int>& nums,int start,int end,int target){
if(start > end)
return-1;
// Finding the mid using floor division
int mid = start +(end - start)/2;
if(nums[mid]== target)
return mid;
// start to mid is sorted
if(nums[start]<= nums[mid]){
if(nums[start]<= target && target < nums[mid]){
return BinarySearch(nums, start, mid -1, target);
}else{
return BinarySearch(nums, mid +1, end, target);
}
}
// mid to end is sorted
else{
if(nums[mid]< target && target <= nums[end]){
return BinarySearch(nums, mid +1, end, target);
}else{
return BinarySearch(nums, start, mid -1, target);
}
#
#include <iostream>
#include <vector>
using namespace std;
int BinarySearch(vector<int>& nums, int start, int end, int target) {
if (start > end)
return -1;
// Finding the mid using floor division
Attach this document to an event, task, or address
You can attach a link to this document to an event in your Calendar, a task in your To Do list or an Address. Check the boxes below for the data you want to
bring into the event’s or task’s description, and then click “Select text to copy” to have the next event or task you create or edit have the document text and link.
