/**

 * 功能：二分查找

 * 基本思想：

 * 假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，

 * 如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的

 * 前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到

 * 找到为止。

 * 作者:徐守威

 */

package com.xushouwei;

public class T8 {

   /**

    * @param args

    */

   public static void main(String[] args) {

      // TODO Auto-generated
method stub

      int arr[]={2,5,7,12,25};

      //实现查找

      BinaryFind binaryfind=new BinaryFind();

      //调用find方法

      binaryfind.find(0, arr.length-1, 12, arr);

   }

}

//定义一个类

class BinaryFind

{

   //这里的val是定义要被查找的数

   public void find(int leftIndex,int rightIndex,int val,int arr[])

   {

      //首先找到中间的这个数

      int midIndex=(rightIndex+leftIndex)/2;

      //得到中间的那个数

      int midVal=arr[midIndex];

      //要不停的查找必须满足左边的数大于右边的数

      if(rightIndex>=leftIndex)

      {

        //如果要找的数比midVal大

        if(midVal>val)

        {

           //在arr数组的左边去找（递归方法实现）

           find(leftIndex,midIndex-1,val,arr);

        }

        else if(midVal<val)

        {

           //在arr数组的右边去找（递归方法实现）

           find(midIndex+1,rightIndex,val,arr);

        }

        else if(midVal==val)

        {

           System.out.println("要找的就是这个数，该数下标为："+midIndex);

        }

      }

   }

}