Find the first occurence of number in the sorted array

Given an array of numbers, search for the first occurrence of the number

This is relatively easy algorithm. But a bit tricky at the same time.
It can be done with log(n) with almost o(1) space complexity


#include 

/*
 * Find the first occurrence of the given number in index.
 * @author http://gullele.com
 */
void main()
{
    int nums[] = {1,1,3,5,8,8,8,10,12,23,23,55};
    int len = sizeof(nums)/sizeof(int);
    int start = 0, end = len-1, search = 8;
    int found_right = -1;
    while ((end - start) > 1)
    {
        if (found_right != -1)
        {
            if (nums[end] != search)
            {
                break;
            }
            found_right = end;
            end -= 1;
            continue;
        }
        int mid = (end + start)/2;
        int val = nums[mid];
        if (val == search)
        {
            end = mid-1;
            found_right = mid;
        }
        else if(val < search)
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    if (found_right != -1)
    {
        printf("found at %d", found_right);
    }
    else
    {
        printf("found No where");
    }
}

See how you would solve these known algorithm problems

Find K Complementary numbers from array Java implementation

Find the pairs that makes K Complementary in the given array java solution

find longest word in the sentence

testing k complementary pairs algorithm with junit

Finding missing numbers from billion sequential number list file

Changing decimal number to its binary equivalent

Flatten nested javascript array

Implement Queue Using two Stacks – JavaScript algorithm

Find longest palindrom from sequence of characters

Check if there are three numbers a, b, c giving a total T from array A

One Comment
  1. Allan Debenedetti

    *Your place is valueble for me. Thanks!…

Leave a Reply to Allan Debenedetti Cancel reply

Your email address will not be published. Required fields are marked *

*
*