Good day! It is another sunny Monday in the Twin Cities of Minneapolis and St. Paul. Had a rather busy weekend. My wife and I visited our youngest son who lives in Madison, WI. Drove last Friday afternoon and returned yesterday. The drive is about 3 ½ hours each way. Traffic was fine in both directions. This time of the year is nice because it is cold enough that bugs do not hit the windshield and warm enough that there are no slippery ice spots on the roads.
It is nice to visit family. My wife and I try to connect with our booth sons every day for a few minutes. We use FaceTime, Jitsi and occasionally just the phone. That said; nothing beats in person visits. I agree that with the COVID pandemic we have gotten used to converse on-line, but technology has ways to go in order to match in person communications.
Last Friday, I woke up around 03:00 AM and noticed that the furnace was running but the incoming air was not warm enough. After some investigation I was able to determine that the furnace was not heating. I assumed that the pilot might be off. I would rather not deal with it, so my wife called for service. They told her that due to the cold weather on Friday they were booked. Since the temperature was not going to dip during the next week or so, it would make sense to have a technician stop by on Monday (that is today). We have an appointment between noon and 03:00 PM CDT. In addition, we would not have to delay our departure on Friday and we will be back late on Sunday.
On our return home, the inside temperature was around 64F. I started the living room fireplace and the ceiling fan. When we were ready to go to sleep, the upstairs temperature was at 72F. Perfect for sleeping on a fall night. Clicked on the remote and the fireplace turned off. The built-in fan continues to circulate air for about 2o-25 minutes after being shut down.
This morning I woke up around 05:30 AM and turned on the upstairs fireplace and the ceiling fan. After breakfast I shut it down and turned on the lower level fireplace and ceiling fan. My office is downstairs. After showering and getting dressed I went down to a nice and toasty office. I decided to turn off the fireplace.
Today I decided to give a try to the 14 Day Study Plan to Crack Algo by LeetCode. It seems that I have already solved some of the problems presented in that section. I decided to try solving all the problems. You never know when you will learn something new.
The first problem is LeetCode 704 Binary Search which is ranked as Easy. I gave this problem a try sometime ago. If interested in the recursive approach I used at the time, you could check Binary Search in Java post in this blog.
The idea is to implement the binary search algorithm. We will implement it using an iterative approach which seems to produce better running times when compared to recursive calls. In addition, recursive approaches make use of considerable stack space. Depending on the size of the array to search, you could possibly run out of stack space. That cannot occur when you use an iterative approach.
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You `must` write an algorithm with O(log n) runtime complexity. Constraints: o 1 <= nums.length <= 104 o -104 < nums[i], target < 104 o All the integers in nums are unique. o nums is sorted in ascending order.
It seems we are provided as input an int[] array and a target integer value. The constraints for the size of the array and the values it can hold are provided. Note that a linear search would not be accepted as a solution. The solution must be O(n log n) runtime. A brute force linear search would not do the trick because it would be O(n).
We will solve this problem on one of my computers which would require a simple test scaffold that would read the two input lines, declare and populate the int[] array and the target value, call the function of interest and display the result. In order to avoid such tasks I would suggest using the on-line IDE provided by LeetCode. We will write a test scaffold which IS NOT PART OF THE SOLUTION.
We will attempt our solution using the Java programming language and the VSCode IDE on a Windows computer.
-1,0,3,5,9,12 9 main <<< nums: [-1, 0, 3, 5, 9, 12] main <<< target: 9 <<< m: 2 <<< l: 3 m: 2 r: 5 <<< m: 4 main <<< output: 4 -1,0,3,5,9,12 2 main <<< nums: [-1, 0, 3, 5, 9, 12] main <<< target: 2 <<< m: 2 <<< l: 0 m: 2 r: 1 <<< m: 0 <<< l: 1 m: 0 r: 1 main <<< output: -1 1 1 main <<< nums: [1] main <<< target: 1 main <<< output: 0 1 2 main <<< nums: [1] main <<< target: 2 main <<< output: -1 2,3,4,10,40 10 main <<< nums: [2, 3, 4, 10, 40] main <<< target: 10 <<< m: 2 <<< l: 3 m: 2 r: 4 <<< m: 3 main <<< output: 3 2,3,4,10,40 -2 main <<< nums: [2, 3, 4, 10, 40] main <<< target: -2 <<< m: 2 <<< l: 0 m: 2 r: 1 <<< m: 0 <<< l: 0 m: 0 r: -1 main <<< output: -1 2,3,4,10,40 50 main <<< nums: [2, 3, 4, 10, 40] main <<< target: 50 <<< m: 2 <<< l: 3 m: 2 r: 4 <<< m: 3 <<< l: 4 m: 3 r: 4 main <<< output: -1 1,2,3,4,5,6 7 main <<< nums: [1, 2, 3, 4, 5, 6] main <<< target: 7 <<< m: 2 <<< l: 3 m: 2 r: 5 <<< m: 4 <<< l: 5 m: 4 r: 5 <<< m: 5 <<< l: 6 m: 5 r: 5 main <<< output: -1 1,2,3,4,5,6 1 main <<< nums: [1, 2, 3, 4, 5, 6] main <<< target: 1 <<< m: 2 <<< l: 0 m: 2 r: 1 <<< m: 0 main <<< output: 0 1,2,3,4,6,7 5 main <<< nums: [1, 2, 3, 4, 6, 7] main <<< target: 5 <<< m: 2 <<< l: 3 m: 2 r: 5 <<< m: 4 <<< l: 3 m: 4 r: 3 <<< m: 3 <<< l: 4 m: 3 r: 3 main <<< output: -1
We are provided with two input lines. The first line holds the values for the `nums` int[] array. The second line contains the value for the `target` which we should look for in the `nums` array.
It seems that our test scaffold reads the two lines and populates the proper variables. The contents of the variables are displayed to make sure all is well so far.
Our test code then seems to invoke the function of interest which displays some values while performing the binary search. When all is said and done, the test code displays the output value.
public int search(int[] nums, int target) {
}
The signature for the function of interest takes the sorted array of integers in the int[] array `nums` and the `target` value that we need to search for in the array. Note that we are to return the index in the `nums` array if the target value is found; otherwise we return a -1 indicating that the `target` value was not found in the search.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read nums 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 function of interest and display output ****
System.out.println("main <<< output: " + search(nums, target));
}
Our test code which IS NOT PART OF THE SOLUTION seems to match closely our description of how the test code handles the input data and returns a result. I believe there is not much to add to the previous description at this time.
/**
* Given an array of integers nums which is sorted in ascending order,
* and an integer target, write a function to search target in nums.
* If target exists, then return its index. Otherwise, return -1.
*
* 47 / 47 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 51.8 MB
*
* Execution: O(n log(n)) - Space: O(1)
*/
static public int search(int[] nums, int target) {
// **** sanity check(s) ****
if (nums.length == 1) return nums[0] == target ? 0 : -1;
// **** initialization ****
int l = 0;
int r = nums.length - 1;
int m = 0;
// **** search for the target value ****
while (l <= r) {
// **** compute mid ****
m = l + (r - l) / 2;
// ???? ????
System.out.println("<<< m: " + m);
// **** check if target found ****
if (target == nums[m]) return m;
// **** update range to continue search ****
if (target < nums[m])
r = m - 1; // go left
else
l = m + 1; // go right
// ???? ????
System.out.println("<<< l: " + l + " m: " + m + " r: " + r);
}
// **** target NOT found ****
return -1;
}
Our function of interest starts by performing a sanity check. If we are provided with an array containing a single value, we could check it and return the result without having to perform further checks. Not sure we need it; but in general I like to perform sanity checks before further diving into a solution.
The next section initializes the variables we will use to perform the binary search. The well known binary search algorithm uses three variables. We need a `left` and a `right` to keep track of the current range in the array we are processing, and a `middle` to keep track of the middle position in such a range.
We are now ready to start the actual binary search. We use a loop to repeat the process and to determine when the search ends.
In the loop we start by computing the midpoint in the current range. We check if the `target` value was found. If so we return the value of `m`.
If the `target` value has not been found we need to split the array into two parts. If the `target` is smaller than the value in the `nums[m]` we need to search toward the left of the array; otherwise we need to continue the search toward the right in the array. The proper `l` or `r` variable value is updated and we are ready to repeat the process in the next loop. Of course if the `l` value is <= than the `r` value, we did not find the `target` in the `nums` array.
The way the `m` value is updated depends on the range of possible values. In our requirements such values are constrained. We could have replaced such a line with `m = (l + r) / 2` and it would work fine. If you try larger arrays you could run into overflows which would cause the algorithm to fail. If interested in a better explanation for this you could find one in Binary Search (https://www.geeksforgeeks.org/binary-search/) by GeeksforGeeks.
That is all she wrote. This solution was accepted by LeetCode. The comments section in the function of interest provides additional information regarding performance.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
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