Given
an array and an element, search the element x in the array using minimum number
of comparisons.
/**This is generic
algorithm which takes 2n+1
* comparisons(worst case) to search element.
*/
private static int searchElementUsingGenericAlgo(int[]
array, int
value) {
int idx = -1;
int length = array.length;
for (int
i = 0;i<length; i++) { /* n+1 comparisons.
*/
if(value == array[i]) { /* n comparisons.
*/
idx = i;
break;
}
}
return idx;
}
This
algorithm is developed to return the element index in 2n+1 comparison in the
worst case.
Approach:
To
avoid the comparison that is taking place in the loop.
Algorithm:
1.
Check that the last element in the array is equal to searched element.
a. YES, element index is found, return the
index.
b. NO, Take back up of last element and put
the searched element on last index of array.
2.
Search for element with Infinite loop (without termination condition) and break
when the element is found
a. If element is found on last index, this
is the element put by us to terminate the search and this signals that element
not found in the array.
b. If element found other than last index,
set the backup to last index and return the index.
public class MinComparison {
/**This algorithm is developed to return
the
*
element index in n+1 comparison in the worst case.
*
Approach: To avoid the comparison that is taking place in the loop.
*
Steps:
* 1.
Check that the last element in the array is equal to searched element.
* a.
YES, element index is found, return the index.
* b.
NO, Take back up of last element and put the searched element on last index of
array.
* 2.
Search for element with Infinite loop(without termination condition) and break
when the element is found
* a.
If element is found on last index, this is the element put by us to terminate
*
the search and this signals that element not found in the array.
* b.
If element found other than last index, set the backup to last index and return
the index.
**/
private static int searchElement(int[] array, int
value) {
int idx = -1;
int length = array.length;
int backup = array[length-1];
if(backup==value) {
return (length-1);
}
array[length-1] = value;
for (int
i = 0;; i++) {
if(value == array[i]) {
idx = i;
break;
}
}
if(idx==length-1) {
idx = -1;
}
return idx;
}
public static void main(String[] args) {
int value = 1;
int [] array = {4, 6, 1, 5, 8};
int index = searchElement(array, value);
System.out.println("Element index in array "+index);
}
}
This
algorithm is developed to return the element index in n+1 comparison in the
worst case.
No comments:
Post a Comment