A binary search algorithm (or binary chop) is a technique for finding a particular value in a linear array, by ruling out half of the data at each step, widely but not exclusively used in computer science.
A binary search finds the median, makes a comparison to determine whether the desired value comes before or after it, and then searches the remaining half in the same manner. Another explanation would be: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half.
Its running time is O(logn).
using namespace std;
//Divide and conquer strategy - Binary Search
/*This algorithm is the simplest application of divide and conquer.
It finds a particular value in a linear array by ruling out half
of the data at each step.A binary search finds the median, makes
a comparision to determine whether the desired value comes before or
after it, and then searches the remaining half in the same manner.
However, the binary search algorithm applies only to sorted arrays.*/
int sorted_array[100];
int i=0;
int binary_search(int target)
{
int first = 0;
int last = i-1;
int mid;
while(first<=last) //while we haven’t reached the end of
{
mid = (first+last)/2; //rule out half of the data by spliting the array
if(sorted_array[mid]==target) //if we have found the target
return mid;
else if(sorted_array[mid]>target)
last = mid-1; //the desired value is in the lower part of the array
else
first = mid+1;//the desired value is in the upper part of the array
}
return -1; //there is no such element in the array
}
int main()
{
int j, n;
while(cin>>j)
sorted_array[i++]=j;
while(cin>>n) //search for an element n in the array
{
int result = binary_search(n); //position of the element n in the array
cout<<result<<endl;
}
}
Binary search is good algorithm for searching in a sorted array but can not be applied to unsorted list.
Hi there
some free/libre programming books:
Programming Languages (by Scott F. Smith):
http://www.cs.jhu.edu/~scott/plbook/book/book.pdf
Programming Languages: Application and Interpretation:
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/PDF/plai-2006-01-15.pdf
Thanks,
Very nice explaination
Should the variable i not be set to the length of the array? in the above evample it it set to 0…this would then fail the “while(first
Very good explaination. An other SIte I would like to share with ya is in the link above.
“Should the variable i not be set to the length of the array? in the above evample it it set to 0…this would then fail the “while(first”
while(0
Hey!!! Why are you putting the binary search algorithm in tree format? What you have presented is the binary search tree one….