二分查找.md

从数组的查找方式中我们知道了线性查找，线性查找就是从数组中挨个查找元素，判断元素是否在数组中存在。不管数组有序还是无序，这种查找的方式性能极其低下，所耗费的时间复杂度为 O(N)。

那么已知一个数组已经是有序的了，如何确定给定的元素是否在数组中存在呢？下面将介绍一种针对有序数组查找的算法，该算法在性能上比线性查找高出数倍。

二分查找

所谓二分查找，就是将一组数据分成 2 部分进行查找，在算法书里面也称为折半查找。

用我们小时候玩的一个游戏来解释比较贴切。比如：小红心里想一个【1，100】之间的一个数字，由小明来猜。不管猜对猜错，小红都会给出相应的提示。我们比如小红想到的数字是 80

小明：50

小红：小了

小明：75

小红：小了

小明：82

小红：大了

就这样一直猜下去，直到猜中为止。

注意到上面的猜数字，每次猜数都是取的中间值，因为每次猜数都可以排除一半的数字，所以这大大加快了找数的时间。

有序数组相比常规数组的一大优势就是它除了可以使用线性查找外，还可以使用二分查找。常规数组因为无序，所以不可能使用二分查找。

以下是二分查找的 Java 代码的实现：

传统方式实现二分查找

public static int middleSearch(int[] target, int value){
  if(target == null){
    return -1;
  }

  //中间位置的索引
  int middleIndex;
	//起始位置的索引
  int startIndex = 0;
  //结束位置的索引
  int endIndex = target.length-1;
  do {
    	//每次中间位置的索引 = 起始未知的索引+结束位置的索引的和除以 2
    	middleIndex = (startIndex+endIndex)/2;
    	//判断数组中间位置的索引的值是否等于给定的值
    	if(target[middleIndex] == value){
        	//给定就返回
      		return middleIndex;
    	} else if(target[middleIndex] > value){
      		//中间索引位的值大于给定的值，调整 endIndex，取左边的数组
      		endIndex = middleIndex -1;
    	} else if(target[middleIndex] < value){ //中间位置的索引小于给定的值，调整 startIndex，取右边的数组
      		startIndex = middleIndex + 1;
    	}
    	System.out.println("中间索引位：" + middleIndex + "||  开始索引位：" + startIndex + "   ||   结束索引位：" + endIndex);
  } while (startIndex <= endIndex); //直到 startIndex <= endIndex 为止
   return -1;
}

使用递归的方式实现二分查找

 public static int middleSearchByRecursion(int[] nums, int value, int beginIndex, int endIndex){
   //开始索引位大于结束索引位时就要跳出循环了
   if(beginIndex > endIndex){
     return -1;
   }

   int middleIndex = (beginIndex + endIndex)/2;
   if(nums[middleIndex] == value){
     return middleIndex;
   } else if(nums[middleIndex] > value){
     endIndex = middleIndex - 1;
   } else if(nums[middleIndex] < value){
     beginIndex = middleIndex + 1;
   }
   return middleSearchByRecursion(nums, value, beginIndex, endIndex);
 }

时间复杂度

每次的查找都能直接排除一半的数据，所以二分查找的时间复杂度为 log₂N，一般称之为 O(logN)。