package test;
/*

• 折半查找算法
• 每次取一半的中间数进行比较
• (前提：原数组已经排好序(升序或降序))
• 注意事项：当给 lastIndex = midIndex-1;

•          firstIndex = midIndex+1;
  

• 赋值的时候 只要后面有加减1的时候(一定要加，不然数组中没这个数的时候，无法跳出循环(死循环))
• 当找不到这个数的时候 最后一定会有： firstIndex > lastIndex
  */
  public class HalfSearch {
  public static void main(String[] args) {
  //需要查找的数
  int num = 3;
  //被查找的数组
  int[] arr = new int[]{1,3,7,9,11,77,78,79};
  //下标 0 0 0
  int midIndex = 0;
  int firstIndex = 0;
  int lastIndex = arr.length;
  boolean flag = false;
  //折半算法
  while(flag==false&&firstIndex<=lastIndex){
  midIndex = (firstIndex+lastIndex)/2;
  if(num==arr[midIndex]){
  System.out.println("找到了您要找的数！它的下标是："+midIndex);
  flag = true;
  }
  if(num<arr[midIndex]){
  lastIndex = midIndex-1;
  }
  if(num>arr[midIndex]){
  firstIndex = midIndex+1;
  }
  // System.out.print("mid :"+midIndex);
  // System.out.print("first: "+firstIndex);
  // System.out.print("last: "+lastIndex);
  }
  //用arr[midIndex]判断值是否相等也可以
  if(flag==false){
  System.out.println("sorry,i can’t found it!");
  }
  }
  }