【密--码--破--译】暴力查找与二分查找

【密--码--破--译】暴力查找与二分查找

暴力查找与二分查找

文章目录

​​暴力查找与二分查找​​​​一.前言​​

​​1.1两种算法的介绍​​

​​二.算法图解​​

​​2.1例题引入与剖析​​

​​三.总结​​

一.前言

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

1.1两种算法的介绍

暴力查找 暴力查找是指依次遍历元素查找对应元素，常用于线性表元素的查找。我们大学学习《算法数据结构》一定会和它打交道的。最常见的运用就是数组元素的遍历啦！一维数组就是计算机内存开辟的连续单元内存，可以以此存入元素，和链表及其队列的差别也在于此。暴力查找在时间复杂度和空间复杂度上不占优势，当数据量庞大的时候，对计算机执行性能就会有较高要求。二分查找 二分查找又叫做折半查找。发挥计算机死板计算，可以灵活开辟内存计算的优势，让计算机对顺序表分别从头部，中间和尾部进行遍历比较。其查找效率高于上面介绍的算法。两种算法使用条件：

顺序表线性表+一维数组

二.算法图解

2.1例题引入与剖析

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

这道题有两个隐藏条件：

顺序表线性表+一维数组

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

class Solution { public int search(int[] nums, int target) { int res=0; for(int i=0;i

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

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

三.总结

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。