【Java】二分查找

用java代码实现二分查找

注意：二分查找的前提时数组已经有序了

二分查找思想：

1.组中找到一个最左边的下标 left=0；找到最右边的下标right=长度-1（左闭右闭区间），再设一个中间值mid=left+(right-left)/2;2.循环时，左边要小于等于右边（左闭右闭时[left,right]),左边小于右边（左闭右开时[left,right) );3.当查找的值比mid大时，左边的下标移mid的下一位：left=mid+1;4.当查找的值比mid小时，右边的下标移到mid的上一位，right=mid-1(左闭右闭时），right=mid(左闭右开时）；5.如果找到的话，返回下标，如果没有找到，返回-1 public class Practice{ //二分查找数组已经有序 public static int binarySearch(int [] array,int key){ int left=0; int right=array.length-1; while(left<=right){ int mid=left+(right-left)/2; //防止溢出 if(key>array[mid]){ left=mid+1; } else if(key<array[mid]){ right=mid-1; } else{ return mid; } } return -1; } public static void main(String[] args){ int [] array={1,2,3,4,5,6,7}; int y=binarySearch(array,2); if(y==-1){ System.out.println("没有找到这个数"); } else{ System.out.println("下标为:"+y); } } }

二分查找的递归形式：

import java.util.Scanner; public class Main { //实现递归的二分算法 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int [] array = new int[n]; for(int i = 0; i < n; i++){ array[i] = sc.nextInt(); } int cur = sc.nextInt(); System.out.println(search(array,0, n-1, cur)); } private static int search(int[] array,int start, int end, int cur) { int mid = (start + end) / 2; if(start > end){ return -1; } if(cur > array[mid]){ return search(array, mid + 1, end, cur); } else if(cur < array[mid]){ return search(array, start, mid - 1, cur); } else if(cur == array[mid]){ return mid; } return -1; } }