It is another nice day in the Twin Cities of Minneapolis and St. Paul. The temperature will be in the low 70s. I noticed in the Weather Channel app on my phone that a warning of brush fires has been issued in this area. Based on the temperatures above than normal and precipitation below normal, it was going to happen sooner or later. Hope we get some needed rain soon.
On a separate note the relationship between Israel and Palestine has taken a wrong turn. The last administration in the US was moving forward and had achieved peace between the parties. With the current administration thousands of rockets has been launched into Israel. Interesting but about 20% of the rockets launched have killed the terrorists that launched them. Hopefully both sides will be able to get to a new agreement.
Today I decided to work on LeetCode 33 Search in Rotated Sorted Array. We have worked on a previous problem in this blog named Find Minimum in Rotated Sorted Array (https://www.johncanessa.com/2021/04/29/find-minimum-in-rotated-sorted-array/) with a similar description and hopefully we will use a similar approach.
There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity. Constraints: o 1 <= nums.length <= 5000 o -104 <= nums[i] <= 104 o All values of nums are unique. o nums is guaranteed to be rotated at some pivot. o -104 <= target <= 104 Related Topics: o Array o Binary Search
We are given an array of sorted integers which have been rotated a few times. We are also given a target value which we should look for (find) in the array. We must attempt an answer that performs in O(log(n)). This eliminates a linear search which is O(n) and leaves us with a binary search approach.
You can see that the Related Topics contains binary search.
We will solve the problem using the Java programming language and the VSCode IDE on a Windows 10 computer. We will require a simple scaffold to collect the input values, call the method of interest and display results. If you use the on-line IDE provided by LeetCode you will not need to implement the test code.
class Solution {
public int search(int[] nums, int target) {
}
}
The signature for the method in question shows that we are given the nums integer[] array and a target. Our mission if we wish to accept is to return the index of the target value.
4,5,6,7,0,1,2 0 main <<< nums: [4, 5, 6, 7, 0, 1, 2] main <<< target: 0 main <<< output: 4 main <<< output: 4 1 0 main <<< nums: [1] main <<< target: 0 <<< start: 0 main <<< output: -1 main <<< output: -1 1 1 main <<< nums: [1] main <<< target: 1 main <<< output: 0 main <<< output: 0 1,3,5,6,7,8,9,10 6 main <<< nums: [1, 3, 5, 6, 7, 8, 9, 10] main <<< target: 6 main <<< output: 3 main <<< output: 3 1,3 3 main <<< nums: [1, 3] main <<< target: 3 <<< start: 0 main <<< output: 1 main <<< output: 1 3,5,1 1 main <<< nums: [3, 5, 1] main <<< target: 1 <<< start: 2 main <<< output: 2 main <<< output: 2 5,1,3 1 main <<< nums: [5, 1, 3] main <<< target: 1 main <<< output: 1 main <<< output: 1 1,3,5 1 main <<< nums: [1, 3, 5] main <<< target: 1 main <<< output: 0 main <<< output: 0 3,5,1 3 main <<< nums: [3, 5, 1] main <<< target: 3 <<< start: 2 main <<< output: 0 main <<< output: 0
I believe the first two test cases were provided by LeetCode as part of the problem. The rest of test cases also came from LeetCode while experimenting with different approaches.
Our test code reads the values for the array followed on the next line with the value for target. The two values are then displayed.
It seems that we call two implementations of the method of interest.
On the first test case, target 0 is at index 4 in the nums array, so that is the correct answer. The same holds true for the rest of the examples and test cases.
/**
* Test scaffold.
* NOT PART OF SOLUTION
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and create array of int[] ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read target ****
int target = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
System.out.println("main <<< target: " + target);
// **** call method of interest and display result ****
System.out.println("main <<< output: " + search0(nums, target));
// **** call method of interest and display result ****
System.out.println("main <<< output: " + search(nums, target));
}
The test code is quite simple and follows our previous description. Not much more to add.
/**
* Given the array nums after the rotation and an integer target,
* return the index of target if it is in nums,
* or -1 if it is not in nums.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.3 MB, less than 61.12% of Java online submissions.
*/
static int search0(int[] nums, int target) {
// **** sanity check(s) ****
if (nums.length == 1 && target == nums[0])
return 0;
// **** initialization ****
int left = 0;
int right = nums.length - 1;
// **** find start or pivot ****
while (left < right) {
// **** compute mid point ****
int mid = left + (right - left) / 2;
// **** check if target was found ****
if (nums[mid] == target)
return mid;
// **** decide which way to go ****
if (nums[mid] > nums[right])
left = mid + 1; // go right
else
right = mid; // go left
}
// **** ****
int start = left;
left = 0;
right = nums.length - 1;
// ???? ????
System.out.println("<<< start: " + start);
// **** decide which part to search on ****
if (target >= nums[start] && target <= nums[right])
left = start;
else
right = start;
// ???? ????
// System.out.println("<<< left: " + left + " right: " + right);
// **** regular binary search (<=) ****
while (left <= right) {
// **** ****
int mid = left + (right - left) / 2;
// **** ****
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // go right
else
right = mid - 1; // go left
}
// **** target NOT found ****
return -1;
}
This approach implements a binary search. Since binary search only works on a sorted array and we have one or two sorted arrays depending where the rotation pivoted, we need to determine which array are we using to look for the target value.
The first “while” loop is used to locate the sorted array of interest.
The second “while” loop implements a standard binary search. It works without modifications on sorted values.
Please take a look at the execution time shown in the comment section.
/**
* Given the array nums after the rotation and an integer target,
* return the index of target if it is in nums,
* or -1 if it is not in nums.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.3 MB, less than 61.12% of Java online submissions.
*/
static int search(int[] nums, int target) {
// **** sanity check(s) ****
if (nums.length == 1 && target == nums[0])
return 0;
// **** initialization ****
int left = 0;
int right = nums.length - 1;
// **** ****
while (left <= right) {
// **** compute mid ****
int mid = (left + right) / 2;
// **** check if target was found ****
if (nums[mid] == target)
return mid;
// **** left sorted portion ****
if (nums[left] <= nums[mid]) {
if (target > nums[mid] || target < nums[left])
left = mid + 1; // go left
else
right = mid - 1; // go right
}
// **** right sorted portion ****
else {
if (target < nums[mid] || target > nums[right])
right = mid - 1; // go right
else
left = mid + 1; // go left
}
}
// **** target NOT found ****
return -1;
}
This is the code for the second implementation. The code is shorted but somewhat more complex. In this case we check if the target value is on the left or right sorted portion.
Please check the execution time of this method which is in the comments section. It appears that both approaches take about the same time. In my humble opinion, the first one is easy to remember and easier to modify if the problem changes slightly. It seems that there is a third problem which uses a similar approach. Hopefully we will take a look at it in the future.
BTW both implementations run in O(log(n)) as required by LeetCode.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John