【算法导论】二分查找
1. 描述(查找算法):
输入:n个数的一个序列 A = (a1, a2, a3,.....an)和一个值v
输出:下表 i 使得 v=A[i] 或者 v 不在A中出现时,输出 NIL
二分查找的前提是A必须是有序序列, 以下全部假设是A是非降序序列
2. 图解
3. 伪代码
//用递归 BINARY_SEARCH(A, v, low, high) if(low <= high) mid = (low+high)/2 //向下取整 if v == A[mid] return mid; else if v < A[mid] return BINARY_SEARCH(A, v, low, mid-1) else if v > A[mid] return BINARY_SEARCH(A, v, mid+1, high) return NIL //用循环 BINARY_SEARCH(A, v) low = 1 high = A.length while low <= high mid = (low + high)/2 //向下取整 if v == A[mid] return mid else if v < A[mid] high = mid -1 else if v > A[mid] low = mid +1
return NIL
4. 代码实现
java
//用循环 int binarySearch1(int[] A, int v){ int low = 0; int high = A.length; while (low <= high) { int mid = (low + high)/2; if (v == A[mid]) return mid; else if (v < A[mid]) high = mid - 1; else if (v > A[mid]) low = mid + 1; return -1; } //用递归 int binarySearch2(int[] A, int v, int low, int high) { if (low <= high) { int mid = (low + high)/2; if (v == A[mid]) return mid; else if (v < A[mid]) return binarySearch2(A, v, low, mid - 1); else if (v > A[mid]) return binarySearch2(A, v, mid + 1, high); return -1; }
python
# 用循环 def binary_search1(nums, v): low = 0 high = len(nums) while low <= high: mid = int((low + high) / 2) if v == nums[mid]: return mid else: if v <= nums[mid]: high = mid - 1 else: if v > nums[mid]: low = mid + 1 return -1 # 用递归 def binary_search2(nums, v, low, high): if low <= high: mid = int((low + high) / 2) if v == nums[mid]: return mid else: if v < nums[mid]: return binary_search2(nums, v, low, mid - 1) else: if v > nums[mid]: return binary_search2(nums, v, mid + 1, high) return -1
C语言
//用循环 int binary_search1(int arr[], int v, int len) { int low, mid, high; low = 0, high = len-1; while (low <= high) { mid = (low + high) / 2; if (v == arr[mid]) return v; else if (v > arr[mid]) low = mid + 1; else if (v < arr[mid]) high = mid -1; } return -1; } //用递归 int binary_search2(int arr[], int v, int low, int high) { int mid; if (low <= high) { mid = (low + high) / 2; if (v == arr[mid]) return v; else if (v > arr[mid]) return binary_search2(arr, v, mid + 1, high); else if (v < arr[mid]) return binary_search2(arr, v, low, mid - 1); } return -1; }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
@ConfigurationProperties注解对数据的自动封装
@ConfigurationProperties注解对数据的自动封装 @ConfigurationProperties可以对基本数据类型实现自动封装,可以封装格式为yyyy/MM/dd的日期 测试代码: package aat; import java.util.Date; import org.springframework.boot.context.properties.ConfigurationProperties; import org.springframework.stereotype.Component; import lombok.Data; /** * 使用@ConrigurationProperties注解封装配置文件中的数据 */ @Component @Data @ConfigurationProperties(prefix="author") public class TestProperties { private String name; private Integer age; private String phone; private Boolean ...
- 下一篇
Python全栈 Web(概述、HTML基础语法)
Web: 什么是Web? Web就是网页 是一种基于B/S的应用程序 Web应用程序是由多个Servlet、JSP页面、HTML文件以及图像文件等组成 B:Browser 浏览器 S:Server 服务器 —————————————————— C/S C:client 客户端 S:Server 服务器 Web组成: 浏览器:代替用户向服务器发送请求 服务器:接受用户响应 通信协议:规范数据在网络中是如何打包即传递的 HTTP:HyoerText transfer portocal 超文本传输协议 Web服务器: 作用; 接受用户请求并且响应 存储Web信息 具备安全性 产品: Apache Tomcat IIS -Internet Information Server Nginx .... 技术: JSP - Java Server page PHP ASP.net Python Web (Django、Flask..) Web浏览器: 作用: 代替用户向服务器发送请求 作为响应用户的解释引擎,向用户呈现界面 主流产品: 根据浏览器内核/引擎划分 Microso...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果