二分查找（Java语言）非递归

二分查找：

• 二分查找是基于有序序列的查找方法，一开始令【low - high】为整个序列的下标区间，然后每次测试当前【low - high】的中间位置mid=（low + high ）/ 2，判断arr【mid】与查找值的大小。
• 二分查找的高效之处在于，每一步都可以去除当前区间中的一半元素，因此时间复杂度是O（logn），这是十分优秀的。

设计思想：

• 二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。在以下介绍的实现方法中，有序数据集存放在arr数组中，参数key是要查找的数据。
• 此实现过程的实施是通过变量low和high控制一个循环来查找元素（其中low和high是正在查找的数据集的两个边界值）。
• 首先，将low和high分别设置为0和arr.length-1。在循环的每次迭代过程中，将mid设置为low和high之间区域的中间值。
• 如果处于mid的元素比目标值小，将左索引值移动到mid后的一个元素的位置上，即将low=mid+1。即下一组要搜索的区域是当前数据集的上半区。
• 如果处于mid的元素比目标元素大，将右索引值移动到mid前一个元素的位置上，即将high=mid-1。即下一组要搜索的区域是当前数据集的下半区。
• 随着搜索的不断进行，low从左向右移，high从右向左移。一旦在mid处找到目标，查找将停止
• 如果没有找到目标，low和high将重合，退出，返回-1。

/**
 *作者：魏宝航
 *2020年11月29日,下午13:27
 */
import java.util.*;
public class Test{
  public static void main(String[] args) {
    int[] arr=new int[100];
    for(int i=1;i<=100;i++) {
      arr[i-1]=i;
    }
    Arrays.sort(arr);
    int key=37;
    if(binarySearch(arr, key)==-1) {
      System.out.println("该值不存在");
    }
    else {
      System.out.println("该值对应的下标为："+binarySearch(arr, key));
    }
  }
  public static int binarySearch(int[] arr,int key) {
    int low=0;
    int high=arr.length-1;
    while(low<=high) {
      int mid=(low+high)/2;
      if(key<arr[mid]) {
        high=mid-1;
      }
      else if(key>arr[mid]) {
        low=mid+1;
      }
      else {
        return mid;
      }
    }
    return -1;
  }
}