一、递归二分查找代码如下
package com.tool.wpn.quicksort; import android.util.Log; /** * Created by Xi on 2017/8/12. * 递归二分查找 */ public class ArrayOrderRecursion { private long[] orderArray;//有序数组 private int nElems;//数组里元素数量,没插入一个才会增加 public ArrayOrderRecursion(int max){ orderArray=new long[max]; nElems=0; } /** * 数组中元素数量 * @return */ public int size(){ return nElems; } /** * 查找指定元素的位置 * @return */ public int find(long searchKey){ return recFind(searchKey,0,nElems-1); } /** * 递归查找方法 * @param serachKey 被查找元素 * @param lowerRound 最小范围,即查找起点 * @param upperRound 最大范围,即查找尾端 * @return */ private int recFind(long serachKey,int lowerRound,int upperRound){ int curIn;//中间位置 curIn=(lowerRound+upperRound)/2; if(orderArray[curIn]==serachKey)//若中间位置正是要查找的元素 return curIn; else if(lowerRound>upperRound)//若最小起点大于最大尾端,则表明没有找到指定元素 return nElems; else{//继续递归查找 if(orderArray[curIn]>serachKey)//中间位置元素大于被查找的元素,则从中间位置左边的范围继续递归查找 return recFind(serachKey,lowerRound,curIn-1); else//若中间位置的元素小于被查找的元素,则从中间位置右侧继续递归查找元素 return recFind(serachKey,curIn+1,upperRound); } } /** * 插入元素 */ public void insert(long value){ int inseartLoc;//别插入的位置 for(inseartLoc=0;inseartLocvalue)break;//若当前数组元素大于被插入元素,则继续往后移动,寻找位置,直到找到位置 for(int k=nElems;k>inseartLoc;k--){//将inseartLoc后面的元素都往后移动一位 orderArray[k]=orderArray[k-1]; } orderArray[inseartLoc]=value; nElems++; } /** * 展示有序数组 */ public void display(){ StringBuilder sb=new StringBuilder(); sb.append("["); for(int i=0;i 二、主函数调用如下 /** * 递归二分查找 */ private void find_recursion(){ ArrayOrderRecursion orderArray=new ArrayOrderRecursion(100); orderArray.insert(70); orderArray.insert(50); orderArray.insert(93); orderArray.insert(10); orderArray.insert(110); orderArray.insert(112); orderArray.insert(80); orderArray.insert(120); orderArray.insert(180); orderArray.display(); long searchKey=1; if(orderArray.find(searchKey)!=orderArray.size())//找到 Log.v(TAG,"二分递归查找找到指定元素"); else Log.v(TAG,"二分递归查找未找到指定元素"); }
日志打印如下:08-15 10:18:05.977 25472-25472/com.tool.wpn.quicksort V/ArrayOrderRecursion: [10,50,70,80,93,110,112,120,180]
08-15 10:18:05.977 25472-25472/com.tool.wpn.quicksort V/MainActivity: 二分递归查找未找到指定元素