Java实现二分查找算法实例分析
程序员文章站
2024-03-06 08:40:01
本文实例讲述了java实现二分查找算法。分享给大家供大家参考。具体如下:
1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
2. 原理...
本文实例讲述了java实现二分查找算法。分享给大家供大家参考。具体如下:
1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法
实现代码:
public class binarysearch { public static void main(string[] args){ int searcharr[] = new int[1000000]; for(int i=0;i<1000000;i++){ searcharr[i]=i; } system.out.println(binsearch(searcharr,0,searcharr.length-1,99)); system.out.println(binsearch(searcharr,99)); } //递归二分查找 public static int binsearch(int arr[], int start,int end,int sear){ int mid = (end-start)/2 + start; if(sear==arr[mid]){ return mid; } if(start>=end){ return -1; }else if(sear < arr[mid]){ return binsearch(arr,0,mid-1,sear); }else if(sear >arr[mid]){ return binsearch(arr,mid+1,end,sear); } return -1; } //循环二分查找 public static int binsearch(int arr[],int key){ int mid = arr.length/2; int start = 0; int end = arr.length-1; while(start<=end){ mid = (end-start)/2+start; if(key ==arr[mid]){ return mid; }else if(key <= arr[mid]){ end = mid-1; }else if(key >=arr[mid]){ start = mid+1; } } return -1; }
效率比较:
循环二分查找算法的效率高于递归二分查找算法
希望本文所述对大家的java程序设计有所帮助。
上一篇: 自制网页选取本地路径控件(附源码)