当前位置: 首页 > news >正文

企业网站建设推荐兴田德润怎么在百度发帖

企业网站建设推荐兴田德润,怎么在百度发帖,网页打不开qq能上,成都网站搜索优化🔥博客主页: 小扳_-CSDN博客 ❤感谢大家点赞👍收藏⭐评论✍ 目录 1.0 二分查找法的说明 2.0 二分查找实现的多种版本 2.1 二分查找的基础版本 2.2 二分查找的改动版本 2.3 二分查找的平衡版本 2.4 二分查找的官方版本 3.0 二分查找的应用 1…

🔥博客主页: 小扳_-CSDN博客
❤感谢大家点赞👍收藏⭐评论✍
  

 

目录

        1.0 二分查找法的说明

        2.0 二分查找实现的多种版本

        2.1 二分查找的基础版本

        2.2 二分查找的改动版本

        2.3 二分查找的平衡版本

        2.4 二分查找的官方版本

        3.0 二分查找的应用


        1.0 二分查找法的说明

        二分查找法(Binary Search)是一种在有序数组有序列表中查找特定元素的搜索算法。其基本思想是将数组或列表分成两部分,取中间位置的元素进行比较,若该元素等于目标值,则查找成功若该元素大于目标值,则在左半部分继续查找若该元素小于目标值,则在右半部分继续查找。不断重复这个过程,直到找到目标值或查找范围缩小到只剩下一个元素为止。

        需要重点注意的是,使用二分查找的前提必须是数组是有序的或者列表是有序的。

        2.0 二分查找实现的多种版本

        基本来说可以分为基础版本和改动版本、平衡版、官方版本。

        2.1 二分查找的基础版本

        先来讲讲具体的实现吧,需要一个有序的数组 arr[] 或者有序列表,还有拿到需要查找的目标元素 int target

        需要定义一下三种变量:

        第一种,int left ;一开始记录着是最左边的元素的索引,即为 0.

        第二种,int right;一开始记录着是最右边的元素的索引,即为 array.length - 1

        第三种,int mid;记录着是中间的元素的索引,即为(left + right)>>> 1;

        接着先要用 arr[mid] 的元素与 target 进行对比,这时候就会有三种情况,分别做不同的处理,假如 if(arr[mid] < target ),中间的元素小于目标元素时,要对 left 进行 left = mid + 1处理,假如 if(arr[mid] > target ),中间的元素大于目标元素时,要对 right 进行 right = mid - 1处理,假如 if(arr[mid] = target ),这时候就找到了目标元素了,直接返回 mid ,因此这是一个循环的过程,不断缩小范围来寻找目标元素,这一切都需要满足 left <= right 这个条件。

具体代码实现如下:

public class BinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 3;System.out.println(search(arr, target));}public static int search(int[] arr, int target){int left = 0;int right = arr.length - 1;while (left <= right){int mid = (left + right) >>> 1;if (arr[mid] < target){left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;}else {return mid;}}return -1;}
}

运行结果如下:

        目标元素3的索引为1,补充一下,若没有找到的话,这里定义返回为 -1 。

        2.2 二分查找的改动版本

        这个版本在基础版本的基础上进行了三点改动:

        第一点;int right;一开始记录着是最右边的元素的索引,即为 array.length 。

        注意,在基础版本中是需要减1的,而这里直接取元素个数,当然我们都知道这个会出现越界情况,所以才会有第二点改动 。

        第二点;这一切都需要满足 left < right 这个条件。

        这基础版本中循环条件是需要 <= 的条件,这里就不需要了,来分析一下为什么呢?

        原因就在第一点,在 right 索引下的元素是不可取的,重点在<不可取>,仔细品味一下,无论right 在之后的循环中得到的所有索引都是不可取到的元素。

        第三点;假如 if(arr[mid] > target ),中间的元素大于目标元素时,要对 right 进行 right = mid 处理。

具体代码实现如下:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 3;System.out.println(search(arr, target));}public static int search(int[] arr, int target) {int left = 0;int right = arr.length;while (left < right) {int mid = (left + right) >>> 1;if (arr[mid] < target) {left = mid + 1;} else if (target < arr[mid]) {right = mid;} else {return mid;}}return -1;}
}

运行结果如下:

         2.3 二分查找的平衡版本

        相对比与第一、两种,这个版本的效率会更高一点。这种版本的思路就是将范围不断缩小为1,然后获取 left 索引下的元素,来判断是否等于目标元素。

具体代码如下:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 3;System.out.println(search(arr, target));}public static int search (int[] arr, int target){int left = 0;int right = arr.length;while (1 < right - left){int mid = (left + right) >>> 1;if (target < arr[mid]){right = mid;} else  {left = mid;}}if (arr[left] == target){return left;}else {return -1;}}
}

运行结果如下:

        2.4 二分查找的官方版本

直接来看原代码:

        来分析一下,从总体来看,官方的二分查找的实现跟第一种的基本版本是大致相同的,有一点跟基础版本的不同的是,就是返回值。在基础版本中,如果找不到就返回 -1,而这里返回的是 -(low + 1),接下来具体讲解一下。

        第一点low 代表的是插入点,这个值跟 left 的值是一样的。

        第二点,关于负数的说法,一般来说找不到的元素时,会返回负数。

具体代码的实现:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 2;System.out.println(search(arr, target));}public static int search(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = (left + right) >>> 1;if (arr[mid] < target) {left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;} else {return mid;}}return -(left + 1);}
}

运行结果如下:

        来算一下,我们知道 2 在数组中是不存在的,插入点为 1 ,则-(1+1)==  -2,验证了是符合的结果的。

 

        3.0 二分查找的应用

        给出下列数组 int[] arr {1,2,3,3,3,3,5,6,7} 要求返回目标元素3的起始位置与结束位置。

        实现的思路:先找起始位置,首先得先找到目标元素的索引,之后得往左边去找找结束位置也是同理,首先得先找到目标元素的索引,之后得往右边去找

代码如下:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,2,3,3,3,3,5,6,7};int target = 3;System.out.print(findLeft(arr, 3)+" ");System.out.println(findRight(arr, 3));}public static int findLeft(int[] arr,int target){int left = 0;int right = arr.length - 1;int sign = -1;while (left <= right){int mid = (left + right) >>> 1;if (arr[mid] < target){left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;}else {sign = mid;right = mid - 1;}}return sign;}public static int findRight(int[] arr, int target){int left = 0;int right = arr.length - 1;int sign = -1;while (left <= right){int mid = (left + right) >>> 1;if (arr[mid] < target){left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;}else {sign = mid;left = mid + 1;}}return sign;}
}

运行结果如下:

 

http://www.ritt.cn/news/18892.html

相关文章:

  • 女式包包网站建设策划书百度数据平台
  • 沈阳做网站费用南宁seo收费
  • 二级网站怎么建设seo网站优化网站编辑招聘
  • 单页网站系统app推广赚钱
  • 做英语题目的网站深圳谷歌seo推广
  • 淘宝美工做倒计时图片网站百度的营销推广模式
  • 公司官网系统莆田网站建设优化
  • 有哪些做的好的网站18款禁用软件黄app免费
  • 新疆生产建设兵团社保卡激活网站深圳seo优化公司哪家好
  • 东莞网站建设公司百推关键词林俊杰mp3免费下载
  • 做外贸哪几个网站好seo交互论坛
  • 河南高端网站建设写一篇软文多少钱
  • 网站建设-搜遇网络永久不收费免费的软件
  • 济南集团网站建设方案soso搜搜
  • 温州大军建设有限公司网站营销推广的方法有哪些
  • 做网站前台要学哪些清远今日头条新闻
  • 广州荔湾做网站的公司网站怎样被百度收录
  • 建设工程检测网seo的内容主要有哪些方面
  • 深圳网站制作工作室黄山网站seo
  • seo短视频永久入口运营关键词优化排名公司
  • 蓟县做网站万网域名注册查询
  • 邯郸企业网站建设2023年12月疫情又开始了吗
  • iis7如何搭建网站产品推广计划
  • 医院网站如何备案百度网站推广排名
  • 分类信息网站如何建设今日小说搜索百度风云榜
  • 外贸网站源码php国内时事新闻
  • 珠海做网站的网络公司线上营销方式主要有哪些
  • 坪山网站建设服务aso优化师
  • 温州手机网站建设wmwl今日疫情最新消息
  • 福州鼓楼区网站建设免费广告投放网站