CareerCup

Pseudocode:
1) Instantiate current pointer to first position in array
2) Calculate absolute difference between current value and expected value
3) If difference is 0, return current value, else, increment current pointer by the difference
4) Repeat steps 2-4 until difference is not zero and current pointer is less than length of array

public int findElementInArray (int[] input, int expected){
	current = 0;
	difference = abs(input[current]-expected);

	while (difference != 0 && current < input.length){
		difference = abs(input[current]-expected);
		current += difference;
	}

	if (difference == 0){
		return current;
	}

	return -1;
}

Basic idea: Instead of doing a linear search, take advantage of +1/-1 property => Two numbers X & Y need to be at last (X-Y) distance apart in the array.

Algorithm:
1) Runner iterates through the numbers (initialized to begin of array)
2) Calculate absolute difference between current value and lookup value
3) If (difference == 0) return Runner location, else, increment Runner value by the difference -> the optimization part and continue from step 2

C++ code:

#include <iostream>     // std::cout
#include <cmath>        // std::abs
#include <vector>       // std::vector

int determineElementPositionSpecialArray (const std::vector<int>& specialArray, int lookupValue)
{
	int runner = 0;

	while (runner < specialArray.size())
	{
		int offset = std::abs(specialArray[runner]-lookupValue);
		if(offset == 0)
		{
			return runner;
		}
		runner += offset;
	}
	
	return -1;
}

int main()
{
    	std::vector<int> specialArray;
    
    	specialArray.push_back(3);
    	specialArray.push_back(4);
    	specialArray.push_back(5);
    	specialArray.push_back(4);
    	specialArray.push_back(5);
    	specialArray.push_back(6);
    	specialArray.push_back(5);
    	specialArray.push_back(4);
    	specialArray.push_back(3);
    	specialArray.push_back(2);
    
    	std::cout << determineElementPositionSpecialArray(specialArray, 6) << std::endl;
    	std::cout << determineElementPositionSpecialArray(specialArray, 2) << std::endl;
    
    	getchar();
    	return 0;
}

int first_occurence(int * a, int n, int key)
{
    if (!n)
        return -1;
    
    int diff = abs(key - a[0]);
    
    while(diff < n) {
     
        if(a[diff] == key) {
            
            return diff;

        } else {
            
            int t = abs(a[diff] - key);
            diff = diff + t;
        }
    }
    
    return -1;
}

int search(int arr[],int low,int high,int key)
{
    if(low<high)
    {
       if(arr[low]==key)
       return low;
       
       else
       return search(arr,abs(arr[low]-key),high,key);
    }
}

int main()
{
int arr[]={2, 3, 4, 5, 6, 5, 4, 5, 6};
int n=sizeof(arr)/sizeof(arr[0]),i;
i=search(arr,0,n-1,4);
printf("%d",i);

  getch();
  return 0;
  }

Given x (the number to be looked for) and array A with the +-1 property.

One algorithm you can do is.

Set guess_index = 0

Compute the difference D = |x - A[guess_index]|

if D == 0, then we have found it. Otherwise we can skip D-1 elements (as we know they can't be be equal to x), so set guess_index += D and repeat.

Pseudo code

int find(int x, int [] A) {
    uint guess = 0;
    uint D = abs(x - A[guess]);
    while (D > 0) {
        guess += D;
        if (guess >= A.Length()) break;
        D = abs(x - A[guess]);
    }
    return D == 0 ? guess : -1;
}

No clue about the time complexity.

Great question here. So to avoid linear search, you simply employ the absolute value of the difference between your current element, and your guess. This will put you at the earliest position that could hold the desired value. If you find your position is outside of the array length, then the element cannot possibly exist inside of the given list. Here is my solution:

public static int operation(int[] a, int guess){
        int position = 0;
        int diff = 0;
        
        while(a[position] != guess){
            diff = guess - a[position];
            if(diff < 0){diff *= -1;} //absolute value
            position += diff;
            if(position >= a.length){return -1;} //error value not in list
        }
        
        return position;

    }

for (int i = 0; i < array.Count();)
            {
                if (array[i] < valuetofind)
                    i += (valuetofind - array[i]);
                else if (array[i] > valuetofind)
                    i += (array[i] - valuetofind);
                else
                {
                    Console.WriteLine("Found at " + i);
                    break;
                }
            }

read first value
index jump abs(given value - value read) and read value again until end_of_array or abs(given value - new value) is smaller than previous
If abs(delta) smaller, then value occurs in that bounded range

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int input;
int firstOccurence=INT_MAX;

int search(int start,int end,int* array){
// printf("start = %d \n",start);
// printf("end = %d \n",end);

if(start>end){
return -1;
}

if(start == end && array[start] != input ){
return -1;
}

int midval= start+(end-start)/2;
int diff = (array[midval] - input);
if(diff==0){
printf("found");
firstOccurence = (midval<firstOccurence)?midval:firstOccurence;
search(0,midval-1,array);
return midval;
}
diff = (diff<0)?-diff:diff;

int low = midval -2*diff;
int high = midval + 2*diff;

low=(low<start)?start:low;
high=(high>end)?end:high;

//printf("am here");
int left = search(low,midval,array);
int right = search(midval+1,high,array);

return (left<0)?right:left;
}


void main(){

int N;
scanf("%d",&N);
int i=0;
int *array=(int *)malloc(sizeof(int)*N);
for(i=0;i<N;i++){
scanf("%d",array+i);
}
scanf("%d",&input);

int res=search(0,N-1,array);
printf("%d",firstOccurence);

}

public class FindANumber {

	/**
	 * @param args
	 */
	static int[] arr = {2, 3, 4, 5, 6, 5, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2};
	static int value = 3;
	public static void main(String[] args) {
				
		getIndex(0,arr.length - 1 );
		
	}

	private static void getIndex(int i, int j) {
		
		if(arr[i] == value) {
			System.out.println(i);System.exit(0);
		}
		else if(i == j) {
			return;
		}
		else{
			int newIndexI = i + (j-i)/2;
			if(isValidBlock(i,newIndexI)){
				getIndex(i,newIndexI);
			}
			
			if(isValidBlock(newIndexI+1,j)){
				getIndex(newIndexI+1,j);
			}
				
		}
		
		
		
	}

	private static boolean isValidBlock(int i, int j) {
		if ( 1 + (value-arr[i]) + (value-arr[j]) <= ((j-i)+1)) return true;
		else return false;
	}

}

public static void main(String args[]){
int a[]={4, 3, 2, 3, 2, 1, 0, 1, 2, 3, 4, 5};
int number =0;
int first =a[0];
int location =0;
location =find_first_occur( a, number,first,location);
System.out.println("location ="+location+" element ="+a[location]);
}
public static int find_first_occur(int array[],int number,int first,int location){

if(first ==number){
System.out.println(" same number ...and location ="+location);
return location;
}
else if (number > first){
int diff = number -first;
location = location+diff;
first = array[location];
System.out.println("diff ="+diff+" newFirst ="+first+" location ="+location);
location = find_first_occur(array,number,first,location);

}
else{
int diff = first -number ;
location = location+diff;
first = array[location];
System.out.println("diff ="+diff+" newFirst ="+first+" location ="+location);
location = find_first_occur(array,number,first,location);
}
return location;
}

#include<conio.h>
#include<stdio.h>

int main()
{
    int a[50],i,j=0,num,n,count;
    printf("Enter total elements of array:   \n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
     scanf("%d",&a[i]);
     }
     printf("Enter no to be searched:   \n");
     scanf("%d",&num);
     count=num-a[0];
     for(i=1;i<n;i++)
     {
                      if(count==0)
                      {
                                 break;
                      } 
            count=count-(a[i]-a[i-1]);
              j++;     
     }
     printf("element at index-   %d ",j);
    getch();
    return 0;
}

Stupid question, consider this sequence:

int a[] = {0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,1,0,1,0,1};
//good luck not doing a linear search.

import java.util.*;
import java.io.*;
class Find_No
{
	public static void main(String args[])
	{
	
	int arr[] = {1,2,1,2,3,4,3,4,5,4};
	int item;
	System.out.print("enter the item to be searched");
	Console con  = System.console();
	item = Integer.parseInt(con.readLine());
	HashMap map = new HashMap();
	for(int i=arr.length-1;i>=0;i--)
	{
		map.put(arr[i],i);
	}
	System.out.println("location of item is"+map.get(item));
	}
	
	
}

public static int find(int[]a, int num){
	int len = a.length;
	int current = 0;
	while(current>=0 || current<len-1){
		int diff = Math.abs(a[current]-num);
		if(diff == 0) return current;
		else 
			current +=diff;
	}
	return -1;
}

import java.io.*;
class Find_No2
{
	public static void main(String args[])
	{
		int arr[] = {0,1,0,1,0,1,2,1,0};
		int count,var=0,i=1;
		System.out.print("Enter a item to be searched");
		Console con = System.console();
		int item = Integer.parseInt(con.readLine());
		count = item-arr[0];
		if(count==0)
		{
		
			System.out.println("item is at 0 index");
			System.exit(0);
		}
		else
			while(i<arr.length)	 
			{
				var = var + count;
				count = item-arr[var];
				if(count==0)
				{
					System.out.println("item is at index"+var);
					System.exit(0);
				}
				i = var; 
			}
			
		System.out.println("item not found");
	}
}

Let's say the first element in the array is 'A', the number to be found is 'Num' .
Then ,
Loop until
Sum of(Difference of each element in the array with the next element) = (A - Num)

Let's say : 2, 3, 4, 5, 6, 5, 4, 5, 6, 7, 8

To find 8 :

A- Num = 2 - 8 = -6
(2-3) + (3 - 4) +( 4 - 5 )+ (5 - 6 ) + (6 - 5) + (5 - 4) + (4 - 5) + (5 - 6) + (6 - 7) + (7 - 8) = -6

The number is 8 since the difference -6 is found.

#define Max 10 // Array Size

void Search(int A[], int key)
{int i=0,diff=0;
while(i<Max)
{
 if(Arr[i]-key==0)
 {printf("position is %d",i); // the position
 return ;
 }
i=abs(Arr[i]-key)
}
}

#define Max 10 // Array Size

void Search(int A[], int key)
{int i=0,diff=0;
while(i<Max)
{
 if(Arr[i]-key==0)
 {printf("position is %d",i); // the position
 return ;
 }
i=abs(Arr[i]-key)
}
}

#include<iostream>
using namespace std;

int main()
{
    int a[10];
    for(int i=0;i<10;i++)
    cin>>a[i];
    
    for(int i=0;i<10;)
    {                  
    if(a[i]==10){
    cout<<"Found at: "<<i<<endl;
    break;
    }
    else if(a[i]>10)
    i=a[i]-10;
    
    else i=10-a[i];
    }
return 0;
}

int searchIncDecByOne(int *arr, int size, int Num) {
int i = 0;
if (!arr || size <=0)
return -1;
while (i >= 0 && i < size) {
if (arr[i] == Num)
return i;
if (arr[i] < Num)
i +=Num-arr[i];
else
i -=arr[i]-Num;
}
if (i < 0 || i >= size)
return -1;
}

Duplicate question: refer /question?id=18136672

int guesser(int a[],int size,int key){
	int guessIndex = 0;
	while(a[guessIndex] != key && guessIndex < size){
		if(key > a[guessIndex])
			guessIndex += key - a[guessIndex];
		else
		{
			guessIndex += a[guessIndex] - key;
		}
                
	}
        if(guessIndex >= size)  return -1;
	return guessIndex;
}

I implemented a recursive function for the solution. The initial guessIndex =0 and each recursive call, i calculate the offset for a possible jump

public static int findElement(int [] a, int target, int guessIndex){
		if(guessIndex >= a.length ) return -1;
		if(a[guessIndex] == target) return guessIndex;
		int offset = target - a[guessIndex];
		return findElement(a, target, guessIndex+offset);
	}

public static void main(String[] args) {

int[] a = { 5, 4, 3, 2, 3, 4, 5, 6, 5, 6, 7, 8 };

findPosition(a, 6, 0);

}

/* default */static void findPosition(int[] a, int ele, int i) {

if (i > a.length - 1) {
System.out.println("ele not found");
return;
}

if (a[i] == ele) {
System.out.println(i);
return;
}

// Assumption diff is positive..
int diff = 0;

diff = Math.abs(ele - a[i]);

findPosition(a, ele, diff + i);

}

This is sort of interpolation search with average/best case complexity of O(lg(lgn)) iff elements are uniformly distributed. but in worst case the complexity meets O(n). I come up with the following code to solve this problem.

Editing it to mention the test-cast where the complexity meets O(n)

in the following array search for 7.

int[] a = {5,6,5,6,5,6,5,6,5,6,5,6,5,6,7};

Algorithm

static int first_occurance(int key, int[] a) {
		
		int start = 0;
		while (start < a.length) {
			
			int v = Math.abs(key - a[start]);
			if (v == 0)
				return start;
			
			start += v;
		}
		
		return -1;
	}

int findFirstPosition(int *a,int length,int num)
{
	int i=1;
	if( (num%2==0 && a[0]%2==0) || (num%2!=0 && a[0]%2!=0) )
		i=0;
	int diff;
	while(i<length)
	{
		if(a[i]==num)
			return i;
		diff = (num-a[i]) <0 ?(a[i]-num):(num-a[i]);
		i+=diff;
	}
	return -1;
}

My Solution can be, lets take the number series
2 1 2 1 2 3 4
And if we want to find out the position of 3,
1) Start with 2, since 3-2 =1, move 1 position and
2) Find the difference, 3-1 = 2, so move 2 positions.
3) next 3-1 = 2, again move 2 positions
4) Now 3-3 = 0, so we got the solution and its not a linear search.

Hope this should work for all the series

public class Sequence {

	private int[] content = new int[]{9,10,9,8,7,6,7,8,9,10,9,10,9};
	
	public Sequence()
	{
	}
	
	public void process(int value)
	{
		int count = 0;
		int i = 0;
		while( i< content.length)
		{
			if(content[i] == value)
			{
				++count;
				i = i+2;
			}
			else
			{
				int diff = Math.abs(value - content[i]);
				i = i + diff;
			}
		}
		
		System.out.println(count);
	}
	
	public static void main(String[] args) {
			new Sequence().process(6);
	}

}

hi, this is python example:

def lookup(x, array, i = 0):
    if len(array) == i: return None 
    if array[i] == x: return i
    i += abs(x - array[i])
    return lookup(x, array, i)

print(lookup(10, [4,5,6,7,8,9,10]))

where method takes x - value you are looking for and array - list which is searched for the value. It returns index of the value, or None if it cannot be found.

O(logn) solution.

Sharing it via CodeBunk so you could run the code as well.

codebunk.com/bunk#-Ix38C2CNuBKt-JHK5Hf

Tweak the merge sort's merge part such that it stores the earliest location. Time O(logN) since merge takes only O(1) and split takes O(logn)

static int Search(int[] arr, int value)
{
    for (int i = 0; i < arr.Length; i += Math.Abs(value - arr[i]))
    {
        if (arr[i] == value) return i;
    }
    return -1;
}

#include <stdio.h>

int main()
{
int a[]={4,5,6,5,6,7,8,9,10,9,10};
int i=0,first,index=0;
first=a[0];
while(first!=7&&i<11)
{
if(first>a[i+1])
{
--first;
}
else
{
++first;
}




++i;
++index;

}

printf("%d",index);

}

/*
Consider an array of integers wherein each element is +1 or -1 its preceding element. 
Given a number, find the first occurence of this number (index) in this array without using linear search. 

For example, consider the array : 
4 5 6 5 6 7 8 9 10 9 10 (each element in this array is +1 or -1 its preceding element) 

Input : 10 (find first occurence of 10 without using linear search) 
Output : 8

*/

#include<iostream>
using namespace std;

void function(int arr[], int start, int end, int num, int& loc)
{
    if(loc == -1 && start<=end)
    {
        if(start==end && arr[start] == num)
        {
            loc = start;
            return;
        }
        else if(start == end)
            return;
        else if(start+1 == end)
        {
            if(arr[start] == num)
            {
                loc = start;
                return;
            }
            else if(arr[end] == num)
            {
                loc = end;
                return;
            }
        }
        int mid = (start+end)/2;
        function(arr, start, mid, num, loc);
        function(arr, mid+1, end, num, loc);
    }
}
    
int main()
{
    int arr[] = {7, 6, 5, 4, 5, 6, 5, 6, 7, 8, 5};
    int size = sizeof(arr)/sizeof(*arr);
    
    int loc = -1;
    int num;
    cout<<"  Enter number to be found :- ";
    cin>>num;
    
    function(arr, 0, size-1, num, loc);
    
    cout<<"  First location of "<<num<<" is :- "<<loc<<endl;;
    
    system("PAUSE");
    return 0;
}

sites.google.com/site/spaceofjameschen/home/sort-and-search/find-the-first-occurence-of-this-number-index-in-this-array-without-using-linear-search-amazon