java 二分法详解几种实现方法

2024-07-13 10:04:42

字体：大中小

来源：转载

供稿：网友

javascript/25644.html">java 二分法详解几种方法

二分查找(java实现)

二分查找

算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

实现：

1.非递归代码

public static int biSearch(int []array,int a){    int lo=0;    int hi=array.length-1;    int mid;    while(lo<=hi){      mid=(lo+hi)/2;      if(array[mid]==a){        return mid+1;      }else if(array[mid]<a){        lo=mid+1;      }else{        hi=mid-1;      }    }    return -1;  }

2.递归实现

public static int sort(int []array,int a,int lo,int hi){    if(lo<=hi){      int mid=(lo+hi)/2;      if(a==array[mid]){        return mid+1;      }      else if(a>array[mid]){        return sort(array,a,mid+1,hi);      }else{        return sort(array,a,lo,mid-1);      }    }    return -1;  }

时间复杂度为 O(logN)

查找第一个元素出现的位置（元素允许重复）

public static int biSearch(int []array,int a){    int n=array.length;    int low=0;    int hi=n-1;    int mid=0;    while(low<hi){      mid=(low+hi)/2;      if(array[mid]<a){        low=mid+1;      }else{        hi=mid;      }    }    if(array[low]!=a){      return -1;    }else{      return low;    }  }

查询元素最后一次出现的位置

public static int biSearch(int []array,int a){    int n=array.length;    int low=0;    int hi=n-1;    int mid=0;    while(low<hi){      mid=(low+hi+1)/2;      if(array[mid]<=a){        low=mid;      }else{        hi=mid-1;      }    }      if(array[low]!=a){      return -1;    }else{      return hi;    }  }

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

注：相关教程知识阅读请移步到JAVA教程频道。

上一篇：Android 判断真机和模拟器的方法

下一篇：spring boot中使用@Async实现异步调用任务