I wrote a post and shared my practice.
I am searching good ideas to practice. What I think is to write excecutable code for all kinds of ideas, and make it work first; Do not have bias on ideas, do not memorize the solution.
It is fine not coming out optimal solution. The following solution is hard to write compared to the one I wrote in August 22, 2019, avoid middle + 1 or middle -1.
Here is the link.
Case study - given array [3, 1], target = 1
I like to write a case study on [3, 1], target = 1.
So first search, start = 0, end = 1;
middle = 0;
middle index position divides the array into two ranges.
First one is [start, middle - 1], [0,-1], the range is not existing.
Second one is [middle + 1, end], [1, 1], one node is in the range.
First one is not existing. So second one is in ascending order.
So numbers[1] = 1, comparing to target 1, the target is found.
Case study - given array [4, 5, 6, 7, 0, 1, 2], target = 3
I like to write a case study on [4, 5, 6, 7, 0, 1, 2], target = 3.
So first search, start = 0, end = 6;
middle = start + (end - start)/ 2 = 3;
middle index position divides the array into two ranges.
First one is [start, middle - 1], or [0,2], numbers in the range are {4, 5, 6}.
Second one is [middle + 1, end], or [4, 6], numbers in the range are {0, 1, 2}.
First one is in ascending order, target value 3 is not in the range [4,6]. So next search area is start = 4, end = 6, or the array {0, 1, 2}.
middle = start + (end - start)/2 = 5.
two ranges to consider, left one is [4, 4], or array {0}, it is in ascending order, target is not in. So next search area is [6,6], or array {2}.
I like to write some case studies since I learn that algorithm practice without getting hands dirty on concrete example is too risky. I should carefully consider what to choose, how to design, but my goal is to make any idea I thought about reality. Therefore, I can challenge myself to build strength as a problem solver.
Case study - given array [2], target = 3
The reason I like to do a case study is that I came cross TLE error. The base case should include the case, array with one number, but not target value.
What I like to do is to go over my design of diving into two halves, why it is not working for this case.
Array: [2], target = 3
start = 0, end = 0.
middle = start + (end - start)/2 = 0.
so left half [start, middle - 1], or [0, -1], not existed at all.
right half [middle + 1, end], or [1, 0], not existed at all.
Combining the above two cases, there is no work done to handle this case. That is the reason a new base should be added to handle it instead.
// Avoid time limit exceeded bug
if (start == end)
return -1;
Things get complicated?
Because I like to introduce middle - 1 and middle + 1 in binary search, I create extra tasks for me to handle. I also should go over a check list based on common mistakes to help me make the idea work perfectly. Just be patient, and work on a simple test case like given an array [2], target = 3.
Here are highlights:
- Use depth first search, middle is base case; one iteration at least one value will be get rid of, so there is no deadlock.
- Use middle position to divide into two ranges, [start, middle - 1], [middle + 1, end], the left range or right range may not exist at all, since middle - 1 < start may be true.
- Add constraint check in case of index-out-range error, (middle - 1) >= start for leftAsc;
- Add constraint check in case of index-out-range error, (middle + 1 <= end) for rightAsc
- I ran into Leetcode online judge TLE error, test case [4, 5, 6, 7, 0, 1, 2], target 3, so I added two more lines of code to avoid TLE; If the range is 1, return -1. The first of 193 cases is failed.
if(start == end)
return -1;
The following code passes online judge.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _33_Rotated_sorted_Array___Catchup
{
class Program
{
static void Main(string[] args)
{
RunTestcase();
}
/// <summary>
/// TLE - time limit exceeded
/// </summary>
public static void RunTestcase()
{
var result = Search(new int[] {4, 5, 6, 7, 0, 1, 2}, 3);
}
/// modified binary search
public static int Search(int[] numbers, int target)
{
if (numbers == null || numbers.Length == 0)
return -1;
var start = 0;
var end = numbers.Length - 1;
while (start <= end)
{
var middle = start + (end - start) / 2;
var middleValue = numbers[middle];
if (middleValue == target)
return middle;
// Avoid time limit exceeded bug
if (start == end)
return -1;
// two range [start, middle - 1], [middle + 1, end]
// range can be one value only
// Range definition should be added
var leftAsc = (middle - 1) >= start && numbers[middle - 1] >= numbers[start];
var rightAsc = (middle + 1 <= end) && numbers[end] >= numbers[middle + 1];
// missing cases
if (leftAsc)
{
if (isInRange(target, new int[] { numbers[start], numbers[middle - 1] }))
{
end = middle - 1;
}
else
{
start = middle + 1;
}
}
else if (rightAsc)
{
if (isInRange(target, new int[] { numbers[middle + 1], numbers[end] }))
{
start = middle + 1;
}
else
{
end = middle - 1;
}
}
}
return -1;
}
private static bool isInRange(int target, int[] range)
{
return target >= range[0] && target <= range[1];
}
}
}
C# various practices in 2019,
here is the link.
