CareerCup

Simple binary search with a tweak:

public static int searchFirstOccurance(final int[] a, final int key) {
    if (a[0] == key) {
        return 0;
    }

    int l = 0;
    int r = a.length - 1;
    int m = (l + r) / 2;
    int keyPosition = Integer.MAX_VALUE;

    while (l <= r) {
        m = (l + r) / 2;
        if (key == a[m]) {
            keyPosition = Math.min(keyPosition, m);
            r = m - 1;
        } else if (key < a[m]) {
            r = m - 1;
        } else if (key > a[m]) {
            l = m + 1;
        }

    }
    return keyPosition == Integer.MAX_VALUE ? -1 : keyPosition;
}

Worst case would still be O(n/2) or O(n) instead of O(nlogn).
Imagine array as { 1, 1, 1, 1, 1, 1 } find index of 1
here mid would be index 3. Going backwards/forwards to find the first/last index of 1 would be maximum n / 2 traversals. That being said, its going to be O(n)

// Idea: use binary search: if to find first element, end = median - 1.
//          If to find last element, begin = median + 1
int Min(int a, int b)
{
    return (a <= b ? a : b);
}

int Max(int a, int b)
{
    return (a >= b ? a : b);
}

int FindFirstIndex(int *arr, int begin, int end, int element)
{
    int index = -1;
    int med = -1;

    if (arr && begin <= end)
    {
        while (begin <= end)
        {
            med = (begin + end) / 2;
            if (arr[med] == element)
            {
                index = (index == -1) ? med : Min(index, med);
                end = med - 1;
            }
            else
            {
                if (arr[med] < element)
                {
                    begin = med + 1;
                }
                else
                {
                    end = med - 1;
                }
            }
        }
    }

    return index;
}

int FindLastIndex(int *arr, int begin, int end, int element)
{
    int index = -1;
    int med = -1;

    if (arr && begin <= end)
    {
        while (begin <= end)
        {
            med = (begin + end) / 2;
            if (arr[med] == element)
            {
                index = (index == -1) ? med : Max(index, med);
                begin = med + 1;
            }
            else
            {
                if (arr[med] < element)
                {
                    begin = med + 1;
                }
                else
                {
                    end = med - 1;
                }
            }
        }
    }

    return index;
}

Here is my solution in C#

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

namespace AlgoSolution
{
    class BSearch
    {
        static void Main()
        {
            int[] num = new int[] { 1 , 1 , 2 ,2 , 3 ,3, 4 };
            Console.WriteLine(LowerBound(num, 4) + 1);
            Console.WriteLine(UpperBound(num, 3) - 1);
        }
        static int LowerBound(int[] data, int num)
        {
            int min = 0;
            int max = data.Length;
            while (min < max)
            {
                int mid = min + (max - min + 1) / 2;
                if (data[mid] < num)
                {
                    min = mid;
                }
                else
                {
                    max = mid - 1;
                }
            }
            return min;
        }

        static int UpperBound(int[] data, int num)
        {
            int min = 0;
            int max = data.Length;
            while (min < max)
            {
                int mid = min + (max - min ) / 2;
                if (data[mid] > num)
                {
                    max = mid;
                }
                else
                {
                    min = mid + 1;
                }
            }
            return min;
        }
    }
}