search algorithm using sentinel

Question

i am trying to do search algorithm using sentinel which reduce time to 3.87n nanoseconds for example compare to this code

 int search (int t ){

 for (int i=0;i<n;i++)
  if (x[i]==t)
   return i;
  return -1;

}

it takes 4.06 nanoseconds

so i am trying to optimize it here is code

public class Search{

public static int search(int a[],int t){
int i;
int p=0;
 int n=a.length;
int hold;
 hold=a[n-1];
 a[n-1]=t;
  for ( i=0;;i++)
  if (a[i]==t)  break;
    a[n-1]=t;
  if (i==n){
 p= -1;
}

else{

p= i;
}


return p;
}
public static  void main(String[]args){
int t=-1;
int a[]=new int[]{4,5,2,6,8,7,9};
 System.out.println(search(a,t));









}
}

but is show me that 9 is at position 6 which is correct but if t =1 or something else which is not array it show me position 6 too please help

Answer 1

Suppose you look t=-1 in array a = [4,5,2,6,8,7,9]. You ask, why the result is 6. Look,

public class Search {

public static int search(int a[], int t) {
  int i;
  int p=0;
  int n=a.length;  // n = 7
  int hold;
  hold=a[n-1];  // hold = a[6] = 9; a[6] - is the last element.
  a[n-1]=t;  // a[6] = -1;
  for ( i=0;;i++)
    if (a[i]==t)  break;  // it will break, when i = 6, cause a[6] = -1;
  // after this root finished, i = 6.
  a[n-1]=t;  // a[6] = -1; again ^^
  if (i==n){  // i!=n, 6!=7.
    p= -1;
  } else{  // this branch will work.
    p= i;  // p = 6;
  }
  return p;  // return 6;
}