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");
}
}
Allan Debenedetti
*Your place is valueble for me. Thanks!…