Linear search is basically the regular search where we go through each element one by one and find the required match.
Binary Search is based on divide and conquere principle. We basically apply binary search on a sorted list/array. Below are the steps:-
1) Take a sorted array.
2) Create 3 variables : upperValue ; lowerValue ; currentValue
3) Start a while loop inside where we will find the median value by using formula ==> (upperVal+lowerVal/2).
4) If the median value is equal to the value to be searched , then bingo.
5) If not, then we will compare the value with with median. If median is less than value to be searched, than median becomes the new upperValue, if it is more , than median becomes the new lowerValue.
6) Incase of step 4 is not true, than again repeat the process in recursive manner.
Below is the alto without using recursion
Below is the algorithm using recursion
Binary Search is based on divide and conquere principle. We basically apply binary search on a sorted list/array. Below are the steps:-
1) Take a sorted array.
2) Create 3 variables : upperValue ; lowerValue ; currentValue
3) Start a while loop inside where we will find the median value by using formula ==> (upperVal+lowerVal/2).
4) If the median value is equal to the value to be searched , then bingo.
5) If not, then we will compare the value with with median. If median is less than value to be searched, than median becomes the new upperValue, if it is more , than median becomes the new lowerValue.
6) Incase of step 4 is not true, than again repeat the process in recursive manner.
Below is the alto without using recursion
public int find(long searchKey)
{
int lowerBound = 0;
int upperBound = nElems-1;
int curIn;
while(true)
{
curIn = (lowerBound + upperBound ) / 2;
if(a[curIn]==searchKey)
return curIn; // found it
else if(lowerBound > upperBound)
return nElems; // can’t find it
else // divide range
{
if(a[curIn] < searchKey)
lowerBound = curIn + 1; // it’s in upper half
else
upperBound = curIn - 1; // it’s in lower half
} // end else divide range
} // end while
} // end find()
Below is the algorithm using recursion
private int recFind(long searchKey, int lowerBound,
int upperBound)
{
int curIn;
curIn = (lowerBound + upperBound ) / 2;
if(a[curIn]==searchKey)
return curIn; // found it
else if(lowerBound > upperBound)
return nElems; // can’t find it
else // divide range
{
if(a[curIn] < searchKey) // it’s in upper half
return recFind(searchKey, curIn+1, upperBound);
else // it’s in lower half
return recFind(searchKey, lowerBound, curIn-1);
} // end else divide range
} // end recFind()
Efficiency of binary search is O (logN)
No comments:
Post a Comment