Find index of lookup value in an int array

Question:
Find minimum index of lookup value in an int array; which it may contain duplicate values, sorted in ascending order, and shifted randomly.  For example, this array [10,10,10,12,12,12,1,1,2,2,2,3,3,3,3,5,5,5,5,7,7,7,8,8,8,9] shifted 10-12 to the beginning.

Workable solution:


static void Main(string[] args)
        {
            var index = find(new[] { 10, 10, 10, 12, 12, 12, 1, 1, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 7, 7, 7, 8, 8, 8, 9, 10}, 9);
            Console.WriteLine(index);
        }

        static int find(int[] values, int lookup)
        {
            int start = 0;
            int end = values.Length - 1;
            int mid = 0;
            bool isFound = false;

            if (values[0] == lookup)
            {
                return 0;
            }

            while (start <= end && !isFound)
            {
                mid = start + (end - start) / 2;

                if (values[mid] > lookup)
                {
                    if (values[end] > lookup && values[mid] > values[end])
                    {
                         start = mid + 1;
                    }
                    else
                    {
                        end = mid - 1;
                    }
                }
                else if (values[mid] < lookup)
                {
                    if (lookup > values[start] && values[start] > values[mid])
                    {
                        end = mid - 1;
                    }
                    else
                    {
                        start = mid + 1;
                    }
                }
                else
                {
                    isFound = true;
                }
            }

            if (!isFound)
            {
                return -1;
            }

            end = mid;
            while (start < end)
            {
                mid = (start + end) / 2;

                if (values[mid] == lookup)
                {
                    end = mid;
                }
                else
                {
                    start = mid + 1;
                }
            }

            return (values[mid] == lookup ? mid: end);
        }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s