Search a number in an array with one comparison.
Normally use a for loop and use if condition to check the variable is it present in array or not.
Like below code.
But in this one condition has changed, if the element is not in the array we need to add this at last and then return the index.
private static int normalLinear(int arr[], int n){
for(int i=0;i<arr.length;i++){
if(arr[i] == n){
return i;
}
}
arr[arr.length-1] = n;
return arr.length-1;
}
But in above code 2 comparisons are happening, one in for loop (for(int i=0;i<arr.length;i++)) another in if condition(if(arr[i] == n)) , so is it possible to done in one comparison.
Lets try :
private static int linearSearch(int[] arr, int n){
for(int i = 0;;i++){
try{
if(arr[i] == n){
return i;
}
}catch(Exception e){
arr[arr.length-1] = n;
return arr.length-1;
}
}
In above code we are running infinite loop, so if we will get the element in array we will return the index, else we will get ArrayIndexOutOfBoundsException, so here we are using try catch and once we get the exception will add our element at last of the array and return last index.
So in this second example we are doing one comparison where we are running infinite loop.
Normally use a for loop and use if condition to check the variable is it present in array or not.
Like below code.
But in this one condition has changed, if the element is not in the array we need to add this at last and then return the index.
private static int normalLinear(int arr[], int n){
for(int i=0;i<arr.length;i++){
if(arr[i] == n){
return i;
}
}
arr[arr.length-1] = n;
return arr.length-1;
}
But in above code 2 comparisons are happening, one in for loop (for(int i=0;i<arr.length;i++)) another in if condition(if(arr[i] == n)) , so is it possible to done in one comparison.
Lets try :
private static int linearSearch(int[] arr, int n){
for(int i = 0;;i++){
try{
if(arr[i] == n){
return i;
}
}catch(Exception e){
arr[arr.length-1] = n;
return arr.length-1;
}
}
In above code we are running infinite loop, so if we will get the element in array we will return the index, else we will get ArrayIndexOutOfBoundsException, so here we are using try catch and once we get the exception will add our element at last of the array and return last index.
So in this second example we are doing one comparison where we are running infinite loop.
Tags:
Problems