33. Search in Rotated Sorted Array - idea 2

Sept. 4, 2019

I wrote the algorithm using C#, here is the discussion post with title "C# Find pivot index first and then apply binary search practice in 2019".

It is the challenge task to master binary search algorithm. What I did is to ask how to solve the algorithm in mock interview as an interviewer first on Sept. 2, 2019, and then I spent 30 minutes to learn from the interviewee, and then I wrote the solution by myself after the mock interview.

The interviewee has 10 years experience and very good understanding to test his own code, so he thoroughly tested the code in the mock interview. Here is my blog to show his python code.

I took the same approach and wrote a C# solution.

Here are highlights:

1. Failed test case [1, 3], target 2, TLE error; Inside while loop, if/ else if is not good design, the clause else if is potential timeout;
2. Failed test case [], target 5. Array is null or length zero checking is added;
3. Learn design of pivot index search algorithm from the interviewee.
4. Default pivot index search return is 0.

Test cases

I like to write down a few test cases I came cross when I practice the algorithm in 2019.

[], 5 - null exception
[3, 1], target is 1, should return 1
[1, 3], target is 2, good test case to test TLE error, dead loop

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _33_Rotated_Sorted_Array___Sept_2
{
    class Program
    {
        static void Main(string[] args)
        {
            var TLE = Search(new int[]{1, 3}, 2);
            var result = Search(new int[] { 4, 5, 6, 7, 0, 1, 2, 3 }, 3);
            var result2 = Search(new int[] { 0, 1, 2, 3, 4, 5, 6, 7 }, 3); 
            var result3 = Search(new int[] { 3, 1 }, 1);             
        }

        public static int Search(int[] nums, int target)
        {
            if (nums == null || nums.Length == 0)
                return -1;

            var pivot = findPivotIndex(nums);

            var result = runBinarySearch(nums, 0, pivot - 1, target);
            if (result >= 0)
                return result;
            result = runBinarySearch(nums, pivot, nums.Length - 1, target);
            return result;
        }

        public static int runBinarySearch(int[] nums, int start, int end, int target)
        {
            if (start > end || target < nums[start] || target > nums[end])
                return -1;

            while (start <= end)
            {
                int middle = start + (end - start) / 2;
                int middleValue = nums[middle];
                if (middleValue == target)
                    return middle;

                if (target >= nums[start] && target < nums[middle])
                {
                    end = middle - 1;
                }
                else
                {
                    start = middle + 1;
                }
            }

            return -1;
        }
        /// <summary>
        /// using binary search to find pivot index
        /// For example: 
        /// 4 5 6 7 0 1 2 3
        /// index = 4, pivot value can be determined by two ways
        /// compare to left or right
        /// if there is no pivot value, then return 0
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        private static int findPivotIndex(int[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
                return -1;

            int start = 0;
            int length = numbers.Length;
            int end = length - 1;

            while (start <= end)
            {
                int middle = start + (end - start) / 2;

                // think about pivot index value - possible options: middle, middle + 1
                if (middle + 1 < length && numbers[middle] > numbers[middle + 1])
                {
                    return middle + 1;
                }
                else if (middle - 1 >= 0 && numbers[middle - 1] > numbers[middle])
                {
                    return middle;
                }
                else if (numbers[start] <= numbers[middle])
                {
                    start = middle + 1;
                }
                else if (numbers[middle] <= numbers[end])
                {
                    end = middle - 1;
                }
            }

            return 0;
        }
    }
}