import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**测试数据99，231，*/
public class Test {
  private static int wwww;

  @SuppressWarnings("resource")
  public static void main(String[] args) throws IOException {
    List<String> list = addnum();
    for (String string : list) {
      System.out.println("list集合：" + string);
    }
    while (true) {
      System.out.println("输入：");
      // 方法一：强大的Scanner类
      Scanner sc = new Scanner(System.in);
      int number = sc.nextInt();
      System.out.println("输入的是:" + number + "\n---------------------");

      long timeStart = System.currentTimeMillis();
      int tototo = modelOne(list, number, 0, list.size() - 1);
      System.out.println("这个数取值在第：" + (tototo + 1) + "行");
      System.out.println("二分递归查找耗时："
          + (System.currentTimeMillis() - timeStart) + "毫秒"
          + "\n共调用modelOne()函数" + wwww + "次"
          + "\n---------------------");

      long timeStart2 = System.currentTimeMillis();
      int tototo2 = modelTwo(list, number, 0, list.size() - 1);
      System.out.println("这个数取值在第：" + (tototo2 + 1) + "行");
      System.out.println("遍历查找耗时："
          + (System.currentTimeMillis() - timeStart2) + "毫秒"
          + "\n---------------------");

      long timeStart3 = System.currentTimeMillis();
      int tototo3 = modelThree(list, number, 0, list.size() - 1);
      System.out.println("这个数取值在第：" + (tototo3 + 1) + "行");
      System.out.println("二分循环查找耗时："
          + (System.currentTimeMillis() - timeStart3) + "毫秒"
          + "\n---------------------");
    }
    // 方法二：
    // BufferedReader br = new BufferedReader(new
    // InputStreamReader(System.in));
    // System.out.println(br.readLine());
    // 方法三：
    // char i = (char) System.in.read();
    // System.out.println(i);

  }

  /** 二分查找--递归 --key=需要查找的值*/
  public static int modelOne(List<String> list, int key, int start, int end) {
    // 二分查找--递归
    wwww += 1;
     if (key < Integer.valueOf(list.get(start).split("\t")[0])
     || key > Integer.valueOf(list.get(end).split("\t")[1])
     || start > end) {
       System.out.println(start+"---"+end);
     return 0;
     }
    int middle = (start + end) / 2;// 中间位置
    System.out.println("middle" + middle);
    if (key > Integer.valueOf(list.get(middle).split("\t")[1])) {
      if (key <= Integer.valueOf(list.get(middle).split("\t")[0])) {
        return middle;
      } else {
        return modelOne(list, key, middle + 1, end);
      }
    } else if (key < Integer.valueOf(list.get(middle).split("\t")[1])) {
      if (key >= Integer.valueOf(list.get(middle).split("\t")[0])) {
        return middle;
      } else {
        return modelOne(list, key, start, middle - 1);
      }
    } else {
      return middle;
    }
  }

  /** 遍历查找 --key=需要查找的值 */
  public static int modelTwo(List<String> list, int key, int start, int end) {
    if (key < Integer.valueOf(list.get(start).split("\t")[1])
        || key > Integer.valueOf(list.get(end).split("\t")[1])
        || start > end) {
      return 0;
    }
    for (int i = 0; i < list.size(); i++) {
      if (key <= Integer.valueOf(list.get(i).split("\t")[1])) {
        return i;
      }
    }
    return 0;
  }

  /** 二分查找---循环 --key=需要查找的值 */
  public static int modelThree(List<String> list, int key, int start, int end) {
    if (key < Integer.valueOf(list.get(start).split("\t")[0])
        || key > Integer.valueOf(list.get(end).split("\t")[1])
        || start > end) {
      return 0;
    }
    while (start <= end) {
      int middle = (start + end) / 2;// 中间位置
      if (key > Integer.valueOf(list.get(middle).split("\t")[1])) {
        if (key <= Integer.valueOf(list.get(middle).split("\t")[0])) {
          return middle;
        } else {
          // return modelOne(list, key, middle + 1, end);
          start = middle + 1;
        }
      } else if (key < Integer.valueOf(list.get(middle).split("\t")[1])) {
        if (key >= Integer.valueOf(list.get(middle).split("\t")[0])) {
          return middle;
        } else {
          // return modelOne(list, key, start, middle - 1);
          end = middle - 1;
        }
      } else {
        return middle;
      }
    }
    return 0;
  }

  /** 添加数据到list */
  public static List<String> addnum() {
    List<String> list = new ArrayList<String>();
    int counts = 0;
    for (int i = 0; i < 10000; i++) {
      list.add((counts + 1) + "\t" + (counts + 5));
      counts += 5;
    }
    return list;
  }

  /** 添加数据到string[] */
  public static String[] addnum2() {
    List<String> list = new ArrayList<String>();
    int counts = 0;
    for (int i = 0; i < 10000; i++) {
      list.add((counts + 1) + "\t" + (counts + 5));
      counts += 5;
    }
    String[] allStrings = null;
    for (int i = 0; i < list.size(); i++) {
      allStrings[i] = list.get(i);
    }
    return allStrings;
  }
}