数组查找算法：线性查找、二分查找

亦凉 2023-02-28 01:22 30阅读 0赞

# 1，线性查找 #

## 1.1，线性查找基本介绍 ##

*  线性查找就是基本的循环查找，遍历每一个元素进行比对，返回匹配结果

## 1.2，线性查找代码实现 ##

package com.self.datastructure.search;
    
    /** * 线性查找 * * @author PJ_ZHANG * @create 2020-03-13 15:18 **/
    public class SeqSearch { 
    
        public static void main(String[] args) { 
            int[] array = { 45, 832, 456, 76, 32, 17, 89, 456, 56};
            System.out.println(seqSearch(array, 56));
        }
    
        public static int seqSearch(int[] array, int target) { 
            for (int i = 0; i < array.length; i++) { 
                if (array[i] == target) { 
                    return i;
                }
            }
            return -1;
        }
    
    }

# 2，二分查找 #

## 2.1，二分查找基本介绍 ##

*  二分查找的前提条件是目标数组为有序数组
 *  在进行数据查找时，首先确定数组的中间下标`（left + right）/ 2`
 *  用数组中间下标时与目标数据进行匹配，如果匹配到直接返回；如果中间值大于目标值，则以中间下标的左侧数组作为新数组再次进行二分查找；如果中间值小于目标值，则以中间下标的右侧数据作为新数据进行二分查找；**倒序数组相反**
 *  再二分递归查找时，如果找到元素，可以直接退出；如果没有找到元素，如果 left 值大于 right 值，则说明没有找到元素，直接退出

## 2.2，二分查找代码实现 ##

package com.self.datastructure.search;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * 二分查找 * * @author PJ_ZHANG * @create 2020-03-13 15:37 **/
    public class BinarySearch { 
    
        public static void main(String[] args) { 
            int[] array = { 1, 12, 55, 55, 55, 78, 156, 765, 873, 987};
            System.out.println(binarySearchWitAll(array, 0, array.length - 1, 55));
        }
    
        public static List<Integer> binarySearchWitAll(int[] array, int left, int right, int target) { 
            if (left > right) { 
                return null;
            }
            int middle = (left + right) / 2;
            if (target > array[middle]) { 
                return binarySearchWitAll(array, middle + 1, right, target);
            } else if (target < array[middle]) { 
                return binarySearchWitAll(array, left, middle - 1, target);
            } else { 
                List<Integer> lstIndex = new ArrayList<>(10);
                // 获取到目标数据
                lstIndex.add(middle);
                // 左右扫描是因为可能存在相同数据
                // 向右扫描所有数据
                for (int i = middle + 1; i < array.length; i++) { 
                    if (array[i] == target) { 
                        lstIndex.add(i);
                    } else { 
                        break;
                    }
                }
                // 向左扫描所有数据
                for (int i = middle - 1; i >= 0; i--) { 
                    if (array[i] == target) { 
                        lstIndex.add(i);
                    } else { 
                        break;
                    }
                }
                return lstIndex;
            }
        }
    
        /** * 二分查找获取到对应值索引 * @param array 目标数组 * @param left 左索引 * @param right 右索引 * @param target 目标值 * @return */
        public static int binarySearch(int[] array, int left, int right, int target) { 
            if (left > right) { 
                return -1;
            }
            // 二分, 获取到中间索引
            int middle = (left + right) / 2;
            // 大于 向右查找
            if (target > array[middle]) { 
                return binarySearch(array, middle + 1, right, target);
            } else if (target < array[middle]) {  // 小于, 向左查找
                return binarySearch(array, left, middle - 1, target);
            } else { 
                return middle;
            }
        }
    
    }

## 2.3，非递归方式实现二分查找 ##

package com.self.datastructure.algorithm;
    
    /** * 非递归方式实现二分查找 * @author pj_zhang * @create 2020-06-26 16:13 **/
    public class BinarySearchWithoutRecursion { 
    
        public static void main(String[] args) { 
            int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8};
            System.out.println(binarySearchWithoutRecursion(arr, 10));
        }
    
        public static int binarySearchWithoutRecursion (int[] arr, int target) { 
            int left = 0;
            int right = arr.length - 1;
            // 只要left的位置不超过right, 说明有效, 可以继续查找
            for (;left <= right;) { 
                int middle = (left + right) / 2;
                // 找到了, 直接返回
                if (arr[middle] == target) { 
                    return middle;
                } else if (arr[middle] < target) { 
                    // 中值小于目标值, 向右找
                    left = middle + 1;
                } else if (arr[middle] > target) { 
                    // 中值大于目标值, 向左找
                    right = middle - 1;
                }
            }
            // 未找到, 返回-1
            return -1;
        }
    
    }