二分查找（递归和非递归实现）

2023-09-11 阅读 22 评论 0

摘要：当然前提是：有序数列，这里以升序为例！ public class binarySearch {public static void main(String[] args) {int arr[]={1,2,3,4,5,6,7,8,9};int key=9;//int result=binarySearchMethod_noDiGui(arr,key);//非递归实现int result=bi

当然前提是：有序数列，这里以升序为例！

public class binarySearch {public static void main(String[] args) {int arr[]={1,2,3,4,5,6,7,8,9};int key=9;//int result=binarySearchMethod_noDiGui(arr,key);//非递归实现int result=binarySearchMethod_DiGui(arr,0,arr.length-1,key);//递归实现System.out.println("结果："+result);}public static int  binarySearchMethod_noDiGui(int arr[],int key){int left =0;int right=arr.length-1;int mid=(left+right)>>1;while(left<=right){if(arr[mid]==key){return mid;}else if(arr[mid]>key){right=mid-1;}else{left=mid+1;}mid=(left+right)>>1;}return -1;}public static int binarySearchMethod_DiGui(int arr[],int left,int right,int key){int mid=(left+right)>>1;if(left>right){return -1;}if(arr[mid]==key){return mid;}else if(arr[mid]>key){right=mid-1;return binarySearchMethod_DiGui(arr,left,right,key);}else{left=mid+1;return binarySearchMethod_DiGui(arr,left,right,key);}}
}