33. Search in Rotated Sorted Array

I wrote a post and shared my practice.

C# introduce middle -1 and middle + 1 practice in August 23, 2019

Here is the link.

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:

1. Use depth first search, middle is base case; one iteration at least one value will be get rid of, so there is no deadlock.
2. 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.
3. Add constraint check in case of index-out-range error, (middle - 1) >= start for leftAsc;
4. Add constraint check in case of index-out-range error, (middle + 1 <= end) for rightAsc
5. 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.