二分查找算法（递归+非递归）

二分算法步骤描述

前提：有序数组中查找关键词所在的位置

① 首先确定整个查找区间的中间位置 mid = strat+(end-strat)/2

② 用待查关键字key值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找

③ 对确定的缩小区域再按折半公式，重复上述步骤。

一、非递归二分查找算法（用while循环判断）

public static int search(int key,int[] arr){ int start=0; int end=arr.length-1; while(start<=end){ int mid=start+(end-start)/2; if(key<arr[mid]){ end=mid-1; }else if(key>arr[mid]){ start=mid+1; }else{ return mid; } } return -1; }

二、递归二分查找算法

public static int search2(int key,int[] arr,int start,int end){ if(start >end){ return -1; } int mid=start+(end-start)/2; if(key<arr[mid]){ return search2(key,arr,start,mid-1); }else if(key>arr[mid]){ return search2(key,arr,mid+1,end); }else{ return mid; } } 主方法：

public static void main(String[] args) { int arr[]={0,1,3,5,6,7,8,8,9}; int resultPosition=search1(3,arr); int result=search2(3,arr,0,arr.length-1); System.out.println("3这个所在位置："+resultPosition); System.out.println("3这个所在位置："+result); }