暴力查找与二分查找

文章目录

• 暴力查找与二分查找

• 一.前言

• 1.1两种算法的介绍

• 二.算法图解

• 2.1例题引入与剖析

• 三.总结

一.前言

生活中查找的例子数不胜数，比如查字典，找东西等。查找是算法数据结构的基础，重中之重，下文我将向大家介绍两种常见查找算法------ 暴力查找和二分查找。在破译密码学里，最常见的跑字典破译密码多半使用的算法便是暴力破解，让我们一起来回顾一下它的原理吧。

1.1两种算法的介绍

• 暴力查找

  暴力查找是指依次遍历元素查找对应元素，常用于线性表元素的查找。我们大学学习《算法数据结构》一定会和它打交道的。最常见的运用就是数组元素的遍历啦！一维数组就是计算机内存开辟的连续单元内存，可以以此存入元素，和链表及其队列的差别也在于此。暴力查找在时间复杂度和空间复杂度上不占优势，当数据量庞大的时候，对计算机执行性能就会有较高要求。

• 二分查找

  二分查找又叫做折半查找。发挥计算机死板计算，可以灵活开辟内存计算的优势，让计算机对顺序表分别从头部，中间和尾部进行遍历比较。其查找效率高于上面介绍的算法。

• 两种算法使用条件：

1. 顺序表

2. 线性表+一维数组

二.算法图解

2.1例题引入与剖析

在LeetCode的剑指offer系列里有呢么一道例题可以作为我们的学习案列

这道题有两个隐藏条件：

1. 顺序表

2. 线性表+一维数组

其实拿到这个题的时候，我的第一个思路就是暴力查找：【java作为示范语言】

class Solution {
    public int search(int[] nums, int target) {
        int res=0;
        for(int i=0;i<nums.length;i++)
                if(nums[i]==target)
                    res++;

        return res;
            
    }
}

一遍过了，但是看执行效率并不高，于是我用二分查找写了一个：

class Solution {
    public int search(int[] nums, int target) {
       int left = 0, right = nums.length;
        int ans = 0;
        while (left < right){
            int mid = left + ((right - left)/2);
            if (nums[mid] >= target){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        while (left < nums.length && nums[left++] == target){
            ans++;
        }
        return ans;
            
    }
}

暴力查找是很简单的思路，以此遍历思路即可。重点介绍二分法：

取顺序表的中间那个元素mid，然后用中间的元素mid和待查找元素x进

行比较大小，以此改变下次的查找区间，使得下次的查找区间缩短一半，所以它又叫折半查找，这样就可节省一半的时间，极大的提高了效率。

根据题意我手写笔记分析一下题目：

我们根据题意顺序存入以下数据，定义好 left right mid三个指针。

• 在这里用“指针”这个词是不恰当的，但这是我的习惯，更方便与理解。我们学C语言的时候指针概念用的多，在 java里没有指针概念。但我希望大家这么理解，为什么呢？因为指针的“指”向对象是元素的 位置，而不是值！！我一说指针，你的第一反应应该是元素的位置，而不是元素本身。如果我说 定义好 left right mid三个变量，那么你就会理解成元素本身。

• 定义一个计数器变量 ans

• 第一个需要查找的元素是 数字8。先让它和 mid指针指向的元素进行比较，显然 8>7,所以收紧 left指针， left指针指向了下标为3的元素；接着 mid指针又指向 left与 right指针的中间元素。以此循环，循环条件为：

while(left<right){}

三.总结