The Ubiquitous Binary Search | Set 1

// C# program to implement
// the above approach
using System;

class GFG
{

// Returns location of key, or -1 if not found
static int BinarySearch(int[] A, int l, int r, int key)
{
    int m;

    while( l < r )
    {
        m = l + (r-l)/2;

        if( A[m] == key ) // first comparison
            return m;

        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }

    return -1;
}
}

// This code is contributed by code_hunt.

// C# conversion

// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
int BinarySearch(int[] A, int l, int r, int key)
{
    int m;

    while (r - l > 1) {
        m = l + (r - l) / 2;

        if (A[m] <= key)
            l = m;
        else
            r = m;
    }

    if (A[l] == key)
        return l;
    if (A[r] == key)
        return r;
    else
        return -1;
}

// This code is contributed by akashish__

using System;

public class Floor {
    // This function returns the largest value in A that is
    // less than or equal to key. Invariant: A[l] <= key and
    // A[r] > key Boundary: |r - l| = 1 Input: A[l .... r-1]
    // Precondition: A[l] <= key <= A[r]
    static int floor(int[] A, int l, int r, int key)
    {
        int m;

        while (r - l > 1) {
            m = l + (r - l) / 2;

            if (A[m] <= key)
                l = m;
            else
                r = m;
        }

        return A[l];
    }

    // Initial call
    static int floor(int[] A, int size, int key)
    {
        // Add error checking if key < A[0]
        if (key < A[0])
            return -1;

        // Observe boundaries
        return floor(A, 0, size, key);
    }

    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        Console.WriteLine(floor(arr, arr.Length - 1, 3));
    }
}
// This code is contributed by sarojmcy2e

using System;

public class OccurrencesInSortedArray
{
    // Returns the index of the leftmost occurrence of the
    // given key in the array
    private static int getLeftPosition(int[] arr, int left,
                                       int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= key)
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
        return right;
    }

    // Returns the index of the rightmost occurrence of the
    // given key in the array
    private static int getRightPosition(int[] arr, int left,
                                        int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= key)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }

    // Returns the count of occurrences of the given key in
    // the array
    public static int countOccurrences(int[] arr, int key)
    {
        int left = getLeftPosition(arr, -1, arr.Length - 1, key);
        int right = getRightPosition(arr, 0, arr.Length, key);

        if (arr[left] == key && key == arr[right])
        {
            return right - left + 1;
        }
        return 0;
    }

    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 2, 2, 3, 4, 4, 5, 5 };
        int key = 2;
        Console.WriteLine(countOccurrences(arr, key)); // Output: 3
    }
}

using System;

public class Program
{
    public static int BinarySearchIndexOfMinimumRotatedArray(int[] A, int l, int r)
    {
        // Extreme condition, size zero or size two
        int m;

        // Precondition: A[l] > A[r]
        if (A[l] >= A[r])
        {
            return l;
        }

        while (l <= r)
        {
            // Termination condition (l will eventually fall on r, and r always
            // points to the minimum possible value)
            if (l == r)
            {
                return l;
            }

            m = l + (r - l) / 2;

            if (A[m] < A[r])
            {
                // Minimum can't be in the range
                // (m < i <= r), we can exclude A[m+1 ... r]
                r = m;
            }
            else
            {
                // Minimum must be in the range (m < i <= r),
                // we must search in A[m+1 ... r]
                l = m + 1;
            }
        }

        return -1;
    }

    public static int BinarySearchIndexOfMinimumRotatedArray(int[] A, int size)
    {
        return BinarySearchIndexOfMinimumRotatedArray(A, 0, size - 1);
    }

    public static void Main()
    {
        int[] A = { 6, 7, 8, 9, 1, 2, 3, 4, 5 };
        int size = A.Length;

        int minIndex = BinarySearchIndexOfMinimumRotatedArray(A, size);

        Console.WriteLine("The index of the minimum element in the rotated array is: " + minIndex);
    }
}