1.1 线性查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。 但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
1.2 二分查找代码实现
package com.yuanxw.datastructure.chapter22;
import java.util.Arrays;
/**
* 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。
* 但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
*/
public class BinarySearch {
public static void main(String[] args) {
int[] array = new int[]{
-7, -4, -2, 5, 8, 10};
System.out.println("原始数据：" + Arrays.toString(array));
int index = binarySearch(array,0,array.length-1,5);
System.out.println("【二分查找】结果下标位置：" + index);
index = binarySearch(array,10);
System.out.println("【二分查找】非递归方式查找结果下标位置：" + index);
}
/**
* 兩分查找方法
*
* @param array
* @param value
*/
public static int binarySearch(int[] array, int left, int right, int value) {
// 当【left > right】条件成立，表示查找结束
if(left > right){
return -1;
}
// 中间索引
int middle = (left + right) / 2;
// 如果查找到的value比array[middle]小，那么左查找。反之，如果查找到的value比array[middle]大，那么右查找。
if(value < array[middle]){
return binarySearch(array,left,middle-1,value);
}else if(value > array[middle]){
return binarySearch(array,middle+1,right,value);
}else{
return middle;
}
}
/**
* 兩分查找方法
* 非递归方式实现
* @param array
* @param value
* @return
*/
public static int binarySearch(int [] array,int value){
int left = 0;
int right = array.length-1;
while (left <= right){
int middle = (left + right) /2;
if(value == array[middle]){
return middle;
}else if(value > array[middle]){
left = middle + 1;
}else{
right = middle -1;
}
}
return -1;
}
}
执行结果：
原始数据：[-7, -4, -2, 5, 8, 10]
【二分查找】结果下标位置：3
【二分查找】非递归方式查找结果下标位置：5
1.3 二分查找总结
- 算法优点：折半查找的时间复杂度为O(logn)，远远好于顺序查找的O(n)。
- 算法缺点：虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
- 适用场景：二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。