折半查找的递归与非递归算法

2021年09月15日 阅读数:1
这篇文章主要向大家介绍折半查找的递归与非递归算法,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
Java代码 折半查找的递归与非递归算法 _Java 折半查找的递归与非递归算法 _的_02
  1. public class biSearch {
  2. /**
  3. * @param args
  4. * 做者:undoner
  5. /*
  6. 折半查找--当查找表是有序表时,可采用折半查找;
  7. 基本思想:在有序表中,取中间元素做为比较对象,若给定值K与中间记录关键字相等,则查找成功;
  8. 若给定值K小于中间记录的关键字,则在表的左半区继续查找;
  9. 若给定值K大于中间记录的关键字,则在表的右半区继续查找,不断重复,直到查找成功/失败。
  10. */
  11. //折半查找非递归算法
  12. //查询成功返回该对象的下标序号,失败时返回-1。
  13. int BiSearch(int r[],int n,int k)
  14. {
  15. int low=0;
  16. int high=n-1;
  17. while(low<=high)
  18. {
  19. int mid=(low+high)/2;
  20. if(r[mid]==k)
  21. return mid;
  22. else
  23. if(r[mid]<k)
  24. low=mid+1;
  25. else
  26. high=mid-1;
  27. }
  28. return -1;
  29. }
  30. //折半查找递归算法
  31. //查询成功返回该对象的下标序号,失败时返回-1。
  32. int BiSearch2(int r[],int low,int high,int k)
  33. {
  34. if(low<0) low=0;
  35. if(high>=r.length) high=r.length-1; //简单的参数验证
  36. if(low>high)
  37. return -1;
  38. else
  39. {
  40. int mid=(low+high)/2;
  41. if(r[mid]==k)
  42. return mid;
  43. else
  44. if(r[mid]<k)
  45. return BiSearch2(r,mid+1,high,k);
  46. else
  47. return BiSearch2(r,low,mid-1,k);
  48. }
  49. }
  50. public static void main(String[] args) {
  51. biSearch bs=new biSearch();
  52. int r[]={1,2,3,4,5};
  53. System.out.println(bs.BiSearch(r,5,5));
  54. System.out.println(bs.BiSearch2(r,0,4,5));
  55. System.out.println(bs.BiSearch2(r,0,5,5));
  56. }
  57. }


运行:
C:\java>java biSearch
4
4