Ferozeh
Similar Questions
flatten doubly list into array
deletion in binary tree
depth first search
in pre post order traversals
display nodes of a given level in tree
breadth first search
|
Question
|
Difficulty Level:
2
|
Solution
|
Explanation Quality:1
|
This question is often asked on interviews since it is easy to code and shows a
candidate's grasp over search algorithms. Without going into complexities remember
that the time complexity of the binary search algorithm is O(lgn) in worst case.
So the basic idea in binary search is that we discard half the search space in each
iteration. So let's say we have an array with eleven integers. We are given a value,
let's call it targer that we intend to find in the array. A further and most important
condition on binary search is that the array on which we perform the search must
be sorted. So in case of ten integer sorted array we start at the middle element,
if the target is equal to the middle element we end our search and declare success.
If the middle element is less than the target then we only need to search the integers
in the slots from 0 to 4 because our target can only occur in those slots since
the array is sorted. If the middle element is less than the targer then the target
can only occur in the slots from 6 to 10. We iteratively conduct this search until
we hit the target and declare success or we declare failure.
Here's the code for binary search. For simplicity assume our array contains exactly
eleven integers. Note it doesn't matter even if we have an even number of elements.
Lastly, we also need to detect when we reach the end of the two arrays. Here's the
code:
int lower, upper, target;
int BinarySearch(int upper, int lower, int[] array){
if(upper <= lower){
return -1;
}
int middle = upper+lower/2;
if(array[middle] == target){
cout<<"Target Found Declare Success"<<endl;
break;
}
if(array[middle] < target){
lower = ceiling(middle); //ceiling function rounds
up
BinarySearch(upper, lower, array);
}
if(array[middle] > target){
upper = floor(middle); //floor function rounds down
BinarySearch(upper, lower, array);
}
Note that we declare two variables lower and upper which keep track of the search
space that we are currently looking in. We initially set upper to the length of
the array and lower to zero. Also, note the ceiling function and the floor function
which work for instance as ceiling(2.5) would give you 3 and floor(2.5) would give
you 2 back.
|
|