【三】Java编程之实现有序数组二分查找
有序序列二分查找算法基本思想:
例子
有序数组:{1,5,8,9,12,17,23,25,29,34,36,37,40,42,45}
数组下标:{0,1,2,3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14}
查找数5
1.在一个查询区间中,确定区间的中心下标,(length-1)/2 这个例子中心下标是7。
2.查找数跟中心下标的值比较。
查找数=中心数,则找到。
查找数>中心数,在中心下标后的区间中重复步骤1、2。
查找数<中心数,在中心下标前的区间中重复步骤1、2。
import java.util.Scanner; public class BinarySearch { public static void main(String[] args) { int[] arr = {1,5,8,9,12,17,23,25,29,34,36,37,40,42,45}; System.out.println("请输入一个正整数"); Scanner s = new Scanner(System.in); int n = s.nextInt(); System.out.println(binSearch( arr, n,0,arr.length-1)); } public static int binSearch(int[] arr,int n,int start,int end){ int currInt = (end-start)/2 + start; if(arr[currInt]==n){ return currInt; } if(start>=end){ return -1; } if(arr[currInt]<n){ return binSearch( arr, n,currInt+1,end); } if(arr[currInt]>n){ return binSearch( arr, n,start,currInt-1); } return -1; } }