数据结构（3）基础查找算法——顺序查找、二分查找（JAVA版）

Bertha 。 2023-09-23 15:33 142阅读 0赞

**目录**

3.1.顺序查找

3.2.二分查找

3.2.1.逻辑简介

3.2.2.代码示例

--------------------

## 3.1.顺序查找 ##

顺序查找，时间复杂度是O(n)，逻辑很简单，就是依次遍历一个线性的数据结构判断所要查找的目标数据是否在这个数据结构里。以下是代码实现：

public boolean sequentialSearch(int target){
            int[] array={1,3,5,7,9,11,13,15};
            for(int i=0;i<array.length;i++){
                if(array[i]==target){
                    return true;
                }
            }
            return false;
        }

### 3.2.二分查找 ###

#### 3.2.1.逻辑简介 ####

二分查找，适用的前提是数据结构里的数据是按照升序或者降序有序排列的，时间复杂度是O（log2为底的n）。

其核心思想是折半，要查找的目标数据和当前段的中间位置的数据比较，

如果目标数据>中间位置的数据，说明要查找的目标数据只可能存在于当前段的右半段，那么就直接去右半段查找即可；

如果目标数据<中间位置的数据，说明要查找的目标数据只可能存在于当前段的左半段，那么就直接去左半段查找即可。

一直重复以上的逻辑，不断的折半载折半。

以下是逻辑简介：

准备三个指针left、mid、right，分别指向当前段的起止位置和中间位置。

查找过程停止的两个条件：

*  找到目标数据
 *  left、right相撞

假设要查找的目标元素为3，一共会经历如下两次折半。

![a538c4299c5748adb8d409b274220dc6.png][]

#### 3.2.2.代码示例 ####

public class findDemo {
        int[] array={1,3,5,7,9,11,13,15};
        int left=0;
        int right=array.length-1;
        int mid=array.length/2;
        public boolean binarySearch(int target){
            //递归出口1：如果mid位置的数据是要查找的数据，整个查找过程结束
            if(array[mid]==target){
                return true;
            }
            //递归出口2：如果直到right和left相遇数据都没有查找到，说明数据不存在
            if(right<=left){
                return false;
            }
            //在左半边进行查找
            if(target<array[mid]){
                right=mid-1;
                mid=left+(mid-left)/2;
            }
            //在右半边进行查找
            if(target>array[mid]){
                left=mid+1;
                mid=mid+(right-mid)/2;
            }
            //递归
            return binarySearch(target);
        }
    }

[a538c4299c5748adb8d409b274220dc6.png]: https://img-blog.csdnimg.cn/a538c4299c5748adb8d409b274220dc6.png