**JAVA** public class BinarySearch { /** Use binary search to find the key in th
ID: 3603606 • Letter: #
Question
**JAVA**
public class BinarySearch {
/** Use binary search to find the key in the list */
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;
while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid])
high = mid - 1;
else if (key == list[mid])
return mid;
else
low = mid + 1;
}
return -1 - low;
}
}
1) See the details and trace the method as intrustructed
int [] list = {2,4,7,10,11,45,50,59,60,66,69,70,79}
int i = BinarySearch.binarySearch(list,2 );
int j = BinarySearch.binarySearch(list,11);
int k = BinarySearch.binarySearch(list,12);
int l = BinarySearch.binarySearch(list,1 );
int m = BinarySearch.binarySearch(list, 3);
2)what would happen if we placed (high >= low) in line 7 with (high > low)?
3) Does the method work if there are duplicate elements in the list?
Explanation / Answer
Given list = {2,4,7,10,11,45,50,59,60,66,69,70,79}
Here are the solutions to 3 parts :
1.
a) int i = BinarySearch.binarySearch(list,2 );
Here value of i will be 0
Explanation :
initially : low=0 , high =12
hig>=low
mid = (0+12)/2 = 6
list[6] > 2 => high = mid -1 = 5
high>=low
mid = (0+5)/2 = 2
list[2] > 2 => high = mid -1 = 1
high>=low
mid = (0+1)/2 = 0
list[0] == 2 , 0 will be returned
b) int j = BinarySearch.binarySearch(list,11);
Here value of i will be 4
Explanation :
initially : low=0 , high =12
hig>=low
mid = (0+12)/2 = 6
list[6] > 11 => high = mid -1 = 5
high>=low
mid = (0+5)/2 = 2
list[2] < 11 => low = mid + 1 = 3
high>=low
mid = (3+5)/2 = 4
list[4] == 11 , 4 will be returned
c) int k = BinarySearch.binarySearch(list,12);
Here value of i will be -6
Explanation :
initially : low=0 , high =12
hig>=low
mid = (0+12)/2 = 6
list[6] > 12 => high = mid -1 = 5
high>=low
mid = (0+5)/2 = 2
list[2] < 12 => low = mid + 1 = 3
high>=low
mid = (3+5)/2 = 4
list[4] < 12 , low = mid + 1 = 5
hig>=low
mid = (5+5)/2 = 5;
list[5]>12 , high = mid - 1 = 4
high >= low => no, so break the loop and return -1-low = -1 - 5 = -6
d) int l = BinarySearch.binarySearch(list,1 );
Here value of i will be 0
Explanation :
initially : low=0 , high =12
hig>=low
mid = (0+12)/2 = 6
list[6] > 1 => high = mid -1 = 5
high>=low
mid = (0+5)/2 = 2
list[2] > 1 => high = mid - 1 = 4
high>=low
mid = (0+4)/2 = 2
list[2] > 1 , high = mid - 1 = 1
hig>=low
mid = (0+1)/2 = 0;
list[0] > 1 , high = mid - 1 = -1
high >= low => no , so break the loop and return -1-low = -1 - 0 = -1
e) int m = BinarySearch.binarySearch(list, 3);
Here value of i will be 0
Explanation :
initially : low=0 , high =12
hig>=low
mid = (0+12)/2 = 6
list[6] > 3 => high = mid -1 = 5
high>=low
mid = (0+5)/2 = 2
list[2] > 3 => high = mid - 1 = 4
high>=low
mid = (0+4)/2 = 2
list[2] > 3 , high = mid - 1 = 1
hig>=low
mid = (0+1)/2 = 0;
list[0] < 3 , low = mid + 1 = 1
high >= low => no , so break the loop and return -1-low = -1 - 1 = -2
2.If we placed (high >= low) in line 7 with (high > low) then some of the elements will not be searched.
Explanation :
Let's suppose there is 1 number in the list : 1
No we search for 1 :
low =0 , high = 0
Now while (high > low) condition is not met so it will not enter the loop and number will not be searched
3.This method will work if there are duplicate numbers in the list , but any index can be returned in this case.
Explanation :
Let's suppose there is 3 elemts in the list : 2,2,3
We search for 2
low =0 , high = 2
mid = (0+2)/2 = 1
list[1] == 2 so 1 will be returned ( 1 is returned even though 2 is present at 0 and 1)
**If you have any query , please feel free to comment with details.
**Happy learning :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.