“线性查找”与“二分法查找”

线性查找与二分法查找（也叫拆半查找）是一种在实际工作中用得比较广泛和比较常见的两种查找算法，一般多用于查找数组这种数据存储方式的数据类型。下面通过实际代码来演示 ，如何来使用这两种查询方式来查出指定数组元素的下标索引。

1、代码演示：

package Test;

public class lookupUtil {

    /**线性查找*/
    int[] arr = {9,8,4,6,5,3,1,2,7};//目标数组

    public int linear(int target){
        for(int i = 0; i<arr.length; i++){
            if(arr[i] == target){
                return i;
            }
        }
        return -1; //如果没有这个元素，则返回-1
    }
    
    /**二分法查找*/
    public int linear2(int target){
        int index = 0; //开始位置
        int end = arr.length - 1; //结束位置
        int mid = (index + end) / 2; //中间位置
        while (true){
            if(index >= mid){
                return -1; //如果起始位置大于或等于结束位置，那么这个元素不在这个查找的分区
            }
            if(arr[mid] == target){
                return mid;
            }
            //如果中间位置大于目标元素
            if(arr[mid] > target){
                end = mid -1;
                //如果中间位置小于目标元素
            }else {
                index = mid + 1;
            }
            mid = (index + end) / 2;
        }
    }
}

2、总结（两者区别）：

1、线性查找对要查找的数组元素的顺序和大小没有特别要求。
2、二分法查找要求要查找的数组元素必须要是升序排序的，也就是从小到大的排序顺序。
3、二分法查找与线性查找相比，二分法查找的效率要比线性查找的查找效率更高、更快。线性查找是要查找的目标元素与数组中的所有元素进行逐个对比，耗时较长，而二分法查找，则是从整个数组中分出一个中间值，然后与要查找的目标元素进行比较大小，如果中间值大于要查找的目标值，则从中间值的右边进行对比查找，反之从中间值的左边进行查找，这样就省去了大量无关元素的对比次数，从而大大的降低了查找时间，提高了查询效率。