二分查找又称为折半查找，首先是从有序数组（必须是有序数组）的中间元素开始查找，如果中间元素是查找数，就返回；
如果中间元素大于或者小于查找数，就从大于或小于查找数的一方继续执行二分查找；没找到就返回空，二分查找和传统查找的差别可以看上图
mid=(left+right)/2
static List Index=new ArrayList(); //后面查找元素是多个时使用 public static void main(String[] args) { int arr[]={1,3,5,7,11,11,11,13,17,19,23,29,31,37,41}; Search(arr,0,arr.length-1,11); System.out.println(Index); }
public static int Search(int[] arr,int left,int right,int target){ //退出条件，因为最差的就是只剩下一个数（left==right）,当left>right时，说明已经把数组查找完了 if (left>right){ return -1; } int mid=(left+right)/2; if (arr[mid]>target){ //查找数小于arr[mid],左遍历 return Search(arr,left,mid-1,target); } else if (arr[mid]<target){//查找数大于arr[mid],右遍历 return Search(arr,mid+1,right,target); }else {//找到后返回 return mid; } }
if (arr[mid]>target){ //查找数小于arr[mid],左遍历 return Search(arr,left,mid-1,target); } else if (arr[mid]<target){//查找数大于arr[mid],右遍历 return Search(arr,mid+1,right,target); }else {//找到后返回 Index.add(mid); //先添加找到的这个数 int temp=mid-1; while (true){ //向左循环遍历查找 if (temp<0 || arr[temp]!=target){ break; } Index.add(temp); temp-=1; } temp=mid+1; while (true){ //向右循环遍历查找 if (temp>arr.length-1 || arr[temp]!=target){ break; } Index.add(temp); temp+=1; } return mid; }
法一查找多个用了while循环查找，有人觉得会很繁琐，其实未必，因为有序数组的相同元素是挨着的，如 int arr[]={1,3,5,7,11,11,11,13,17,19,23,29,31,37,41};
else {//找到后返回 Index.add(mid); Search(arr,left,mid-1,target); Search(arr,mid+1,right,target); return mid; }
原文：https://www.cnblogs.com/han200113/p/11743241.html