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

binary tree problems with solution

Implementing tokenizer and adding tokens to the linked list

Array reversal in Recurrsion

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

Changing decimal number to its binary equivalent

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

Find K Complementary numbers from array Java implementation

String Ordered Permutation Algorithm Problem

testing k complementary pairs algorithm with junit

Find longest palindrom from sequence of characters

One Comment
  1. Allan Debenedetti

    *Your place is valueble for me. Thanks!…

Leave a Reply

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

*
*