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

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

Array reversal in Recurrsion

Find longest palindrom from sequence of characters

String Ordered Permutation Algorithm Problem

Check if two strings are anagrams or not

Implementing tokenizer and adding tokens to the linked list

Finding missing numbers from billion sequential number list file

binary tree problems with solution

Changing decimal number to its binary equivalent

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

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 *

*
*