Which of these code snippets can be used to improve the time complexity of the below given code snippet to O(log(N))?
public static int Search(int arr[], int elementToSearch) {
for (int index = 0; index < arr.length; index++) {
if (arr[index] == elementToSearch)
return index;
}
return -1;
}
Options
1.public static int Search(int arr[], int firstElement, int lastElement, int elementToSearch) {
if (lastElement >= firstElement) {
int mid = firstElement + (lastElement - firstElement) / 2;
if (arr[mid] == elementToSearch)
return mid;
if (arr[mid] > elementToSearch)
return Search(arr, firstElement, mid - 1, elementToSearch);
return Search(arr, mid + 1, lastElement, elementToSearch);
}
return -1;
2.public static int Search(int[] integers, int elementToSearch) {
int startIndex = 0;
int lastIndex = (integers.length - 1);
while ((startIndex <= lastIndex) && (elementToSearch >= integers[startIndex]) &&
(elementToSearch <= integers[lastIndex])) {
int pos = startIndex + (((lastIndex-startIndex) /
(integers[lastIndex]-integers[startIndex]))*
(elementToSearch - integers[startIndex]));
if (integers[pos] == elementToSearch)
return pos;
if (integers[pos] < elementToSearch)
startIndex = pos + 1;
else
lastIndex = pos - 1;
}
return -1;
}
3.Both Choice 1 and 2
4.Neither Choice 1 nor 2
