aannenko · June 2, 2024 09:05
diff --git a/RotatedBinarySearch.cs b/RotatedBinarySearch.cs
 Console.WriteLine(RotatedBinarySearch([6, 7, 8, 9, 10, 1, 2, 3, 5], 3)); // 7
 Console.WriteLine(RotatedBinarySearch([1, 1, 1, 1, 1, 1, 2, 1, 1, 1], 2)); // 6

 static int RotatedBinarySearch(int[] ints, int searchedValue)
 {
    var low = 0;
    var high = ints.Length - 1;
    while (low <= high)
    {
        var mid = low + (high - low) / 2;

        if (ints[mid] == searchedValue)
            return mid;

        if (ints[low] == ints[mid] && ints[high] == ints[mid]) // handle duplicates
        {
            low++;
            high--;
        }
        else if (ints[low] <= ints[mid]) // if true, left side is sorted
        {
            if (ints[low] <= searchedValue && searchedValue <= ints[mid])
                high = mid - 1; // searchedValue is in the sorted side
            else
                low = mid + 1; // searchedValue is in the unsorted side
        }
        else // otherwise right side is sorted
        {
            if (ints[mid] <= searchedValue && searchedValue <= ints[high])
                low = mid + 1; // searchedValue is in the sorted side
            else
                high = mid - 1; // searchedValue is in the unsorted side
        }
    }

    return -1;
 }

 /*
 THEORY

 Binary search looks up items in a sorted array in O(log*N) time.
 It logically splits the array in two parts using a pivot and then
 checks if the searched value is equal, less or greater than the pivot.
 If the value is equal to the pivot, it returns the pivot's index.
 If the value is less or greater than the pivot, binary search will
 repeat the search in the corresponding half of the array until it
 finds the searched value. If the value is not found, it returns -1.

 Edge cases.

 1. Array is rotated.
 In this case binary search looks for the sorted part of the array
 on each iteration and checks if the value is expected to be in or
 out of the sorted part, and then narrows the search to that part.

 2. Rotated array has duplicates (e.g. find 2 in [1, 2, 1, 1, 1]).
 In this case previous logic may fail to find the right part where
 the searched value is located (in our case it will pivot on the
 ints[2] and then will narrow the search to the right side from the
 pivot). In order to address this, the code should first repeatedly
 check if the first and the last element of the searched area have
 the same value, and then narrow the search area by excluding those
 elements. Once the first and the last element of the searched area
 are different, proceed with the regular rotated binary search.
 */
	Console.WriteLine(RotatedBinarySearch([6, 7, 8, 9, 10, 1, 2, 3, 5], 3)); // 7
	Console.WriteLine(RotatedBinarySearch([1, 1, 1, 1, 1, 1, 2, 1, 1, 1], 2)); // 6

	static int RotatedBinarySearch(int[] ints, int searchedValue)
	{
	var low = 0;
	var high = ints.Length - 1;
	while (low <= high)
	{
	var mid = low + (high - low) / 2;

	if (ints[mid] == searchedValue)
	return mid;

	if (ints[low] == ints[mid] && ints[high] == ints[mid]) // handle duplicates
	{
	low++;
	high--;
	}
	else if (ints[low] <= ints[mid]) // if true, left side is sorted
	{
	if (ints[low] <= searchedValue && searchedValue <= ints[mid])
	high = mid - 1; // searchedValue is in the sorted side
	else
	low = mid + 1; // searchedValue is in the unsorted side
	}
	else // otherwise right side is sorted
	{
	if (ints[mid] <= searchedValue && searchedValue <= ints[high])
	low = mid + 1; // searchedValue is in the sorted side
	else
	high = mid - 1; // searchedValue is in the unsorted side
	}
	}

	return -1;
	}

	/*
	THEORY

	Binary search looks up items in a sorted array in O(log*N) time.
	It logically splits the array in two parts using a pivot and then
	checks if the searched value is equal, less or greater than the pivot.
	If the value is equal to the pivot, it returns the pivot's index.
	If the value is less or greater than the pivot, binary search will
	repeat the search in the corresponding half of the array until it
	finds the searched value. If the value is not found, it returns -1.

	Edge cases.

	1. Array is rotated.
	In this case binary search looks for the sorted part of the array
	on each iteration and checks if the value is expected to be in or
	out of the sorted part, and then narrows the search to that part.

	2. Rotated array has duplicates (e.g. find 2 in [1, 2, 1, 1, 1]).
	In this case previous logic may fail to find the right part where
	the searched value is located (in our case it will pivot on the
	ints[2] and then will narrow the search to the right side from the
	pivot). In order to address this, the code should first repeatedly
	check if the first and the last element of the searched area have
	the same value, and then narrow the search area by excluding those
	elements. Once the first and the last element of the searched area
	are different, proceed with the regular rotated binary search.
	*/