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

Changing decimal number to its binary equivalent

Find longest palindrom from sequence of characters

Array reversal in Recurrsion

Finding missing numbers from billion sequential number list file

binary tree problems with solution

testing k complementary pairs algorithm with junit

Implementing tokenizer and adding tokens to the linked list

String Ordered Permutation Algorithm Problem

Java solution for checking anagram strings – tell if phrases are anagrams

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 *

*
*