Completely Solved C, C++ Programs Assignment.

 Quick Search Database Videos Tutorials Ebooks Forums FAQ Aboutus Household Industrial Manufacturing Service Shopping Transportation

### Algorithm of binary search

 Filed Under:

Binary Search Algorithms
* The Binary search requires an ordered list.

 Iterative Algorithm
int find (const apvector &list, double target)
// pre: list is sorted in ascending order
//post: ITERATIVE binary search will return the index of the target element, else -1
4. {
5. int mid;
6. int first = 0;
7. int last = list.length( ) -1;
8. while ( first <= last )
9. {
10. mid = (first + last) / 2;
11. if ( list[mid] == target )
12. return mid;
13. if ( list[mid] > target )
14. last = mid - 1;
15. else first = mid + 1;
16. }
17. return -1;
18. }

******************************************************************************************
 Recursive Algorithm
int find (const apvector &list, double target, int first, int last)
// pre: list is sorted in ascending order
//post: RECURSIVE binary search will return the index of the target element, else -1
20. {
21. if (first > last)
22. return -1;
23.
24. int mid = (first + last) / 2;
25. if (list[mid] == target)
26. return mid;
27.
28. if (list[mid] < target)
29. return find(list, target, mid+1, last);
30.
31. return find(list, target, first, mid-1);
32.
33. }
******************************************************************************************

 @import url(http://www.google.com/cse/api/branding.css);