Algorithm of binary search

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. }

******************************************************************************************

Complete Computer Science guide