Java和c++中二分法查找数组元素的实现机制

2024-06-18 23:58
文章标签 java c++ 实现 数组 元素 查找 机制 二分法

本文主要是介绍Java和c++中二分法查找数组元素的实现机制，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Java和c++中二分法查找数组元素的实现机制

在数据结构和算法中，我们会见到二分法查找数组元素这个经典的算法。事实上，二分法也称为折半查找法。该算法的主要机制是：
**（1）**先将数组元素从小到大排列（或者从大到小排列，下面算法是基于小到大排序）
**（2）**有一维数组arr1D[len]，len为数组的长度，首先定义int low =0，int high = len;确定该数组区间的中间位置int mid= (low+high)/2,将查找的值key与arr1D[mid]比较。若相等，查找成功返回此位置的mid；否则确定新的查找区域，继续新二分查找。新的区域可用如下的算法进行：
在low<=high时开始二分寻找， 当 arr1D[mid]>key时，由数组的有序性可知arr1D[i,i+1,……,high]>key,所以key的值只能在新的区间arr1D[low,……，mid-1]中，此时 low 不变，high更新为 high=mid-1；
当arr1D[mid]<key时， 类似上面新的查找区间为arr1D[mid+1,……，high]，此时high不变，low更新为low=mid+1。
每找到新的区间后，mid更新为mid= (low+high)/2 ,将查找的值key与arr1D[mid]比较，若相等，查找成功返回此位置的mid； 若不相等，则当前查找区间将缩小一半，递归继续查找,直到low>high结束查找，,这时若是未找到与key相等的arr1D[mid]，则说明该数组没有key这个元素。
（3） 该算法的时间复杂度为:O(log2n)。

例如给出数组：arr1D={1,13,11,6,4,9};
首先将数组从小到大排序： arr1D ={ 1,4,6,9,11,13}
int low =0；
int high = 6；
int mid= (low+high)/2;即mid = 3, 可知arr1D[mid]=9；
假设查找的元素为 int key =11；
第1次查找：
由于key !=arr1D[mid]，且key>arr1D[mid],则key应该在arr1D[mid+1,high-1 ]中
第2次查找：
此时 low = mid+1=4, 而high =6不变，则mid更新为 mid = (low +high)/2 =5;则arr1D[mid]=13， 由于key !=arr1D[mid]，且key<arr1D[mid],则key应该在arr1D[low,mid-1 ]中
第3次查找：
此时 low = 4不变, 而high =mid-1=4，则mid更新为 mid = (low +high)/2 =4;则arr1D[mid]=11， 由于key =arr1D[mid]=11，则找到该元素key=8,返回索引mid =4,二分法查找结束。

假设查找的元素为 int key =10；
第1次查找：
由于key !=arr1D[mid]，且key>arr1D[mid],则key应该在arr1D[mid+1,high-1 ]中
第2次查找：
此时 low = mid+1=4, 而high =6不变，则mid更新为 mid = (low +high)/2 =5;则arr1D[mid]=13， 由于key !=arr1D[mid]，且key<arr1D[mid],则key应该在arr1D[low,mid-1 ]中
第3次查找：
此时 low = 4不变, 而high =mid-1=4，则mid更新为 mid = (low +high)/2 =4;则arr1D[mid]=11， 由于key !=arr1D[mid]，且key<arr1D[mid],则key应该在arr1D[low,mid-1 ]中,
第4次查找：
此时 low = 4不变, 而high =mid-1=3，则mid更新为 mid = (low +high)/2 =3;则由于此时low<=high不成立，从而结束查找，返回 -1,表示未在arr1D中找到key这个元素。

二分法可以使用递归来实现：

下面是基于c++的代码实现，使用一个动态的一维数组来输入一维数组的值再进行查找测试：

``#include<iostream>
#include<time.h>
using namespace std;
//定义指向一位数组的指针
int *arr1D = NULL;
//定义一维数组的长度
int len = 0;
//要查询的值
int key = -1;
//返回的索引
int index = -1;void Sort()
{//冒泡排序法将数组从小到大排序for (int i = 0; i < len - 1; i++){for (int j = 0; j < len - i - 1; j++){int temp;if (arr1D[j] > arr1D[j + 1]){temp = arr1D[j + 1];arr1D[j + 1] = arr1D[j];arr1D[j] = temp;}}}//打印排序好的数组for (int i = 0; i < len; i++){cout << arr1D[i] << "  ";}cout << endl;
}
//折半查找（二分法查找）,找到元素key返回对应索引，否则返回-1
int search(int *arr, int key, int low, int high)
{//定义一维数组的中间索引int mid = (low + high) / 2;//使用while循环，找到要查询的值直接返回索引while (low <= high){if (arr[mid] == key){//找到key的值返回对应的索引return mid;}//key的值在arr[mid]左侧查找else if (arr[mid] > key){//更新high的值high = mid - 1;//递归继续查找return search(arr, key, low, high);}//key的值在arr[mid]右侧查找else if (arr[mid] < key){//更新low的值low = mid + 1;//递归继续查找return search(arr, key,low, high);}}//未找到返回-1return -1;}
void input()
{cout << "请输入一维数组的长度：" << endl;cin >> len;//給一维数组开辟空间arr1D = new int[len];cout << "请输入一维数组的元素：" << endl;//给一维数组赋值for (int i = 0; i < len; i++){cin >> arr1D[i];}//排序Sort();//多次调试while (true){cout << "请输入要查询的值(按下-1跳出查询)：" << endl;if (key == -1){break;}cin >> key;//查找并返回对应索引index = search(arr1D, key, 0, len);cout << "该元素的索引为：" << index << endl;}
}int main()
{input();system("pause");return 0;
}

下面是基于VS2017 的c++代码的实现截图：在这里插入图片描述

二分法也可以使用非递归来实现：

#include<iostream>
using namespace std;
//一维数组指针
int *arr1D = NULL;
//一维数组的长度
int len = 0;
//要查询的值
int key = -1;
int FindIndex(int *arr,int key,int low,int high)
{//数组长度的中间值int mid = (low + high) / 2;//使用while循环进行判断while (low<=high){//判断key是否与arr[mid]相等if (key==arr[mid]){//找到key的对应索引并返回return mid;}else if(key>arr[mid]){//更新low的值,往mid右侧寻找low = mid + 1;//更新mid的值mid = (low + high) / 2;}else{//更新high的值，往mid左侧寻找high= mid -1;//更新mid的值mid = (low + high) / 2;}}//未找到返回-1return -1;
}
//冒泡排序将数组元素从小到大排序
void sort() 
{for (int i = 0; i < len-1; i++){for (int j = 0; j < len - i - 1; j++) {int temp;if (arr1D[j+1]<arr1D[j]){temp = arr1D[j + 1];arr1D[j + 1]= arr1D[j];arr1D[j] = temp;}}}cout << "排序后的数组为：";for (int k = 0; k < len; k++){cout << arr1D[k] << " " ;}cout << endl;
}
//初始化
void invi()
{cout << "请输入数组的长度" << endl;cin >> len;arr1D = new int[len];cout << "请输入一维数组的元素：";for (int i = 0; i < len; i++){cin >> arr1D[i];}//将数组排序sort();//多次调试while (true){cout << "请输入要查询的值(按下-2跳出查询)：" << endl;cin >> key;if (key == -2){break;}//查找并返回对应索引int index = FindIndex(arr1D, key, 0, len);cout << "该元素的索引为：" << index << endl;}}int main()
{invi();system("pause");return 0;
}

运行截图为：
在这里插入图片描述

对于Java来说，思想也是一样的，不使用递归的代码为：

package Homework;import java.util.Scanner;/*** * 内容： 二分法查找不用递归* * @author 陌意随影* @date:2019年7月10日下午9:48:51*/public class HomeWork17 {public static void main(String[] args) {// 定义并初始化一个一维数组int[] arr = {1,13,11,6,4,9};//排序sort(arr);//多次调试while(true) {Scanner s = new Scanner(System.in);System.out.println("请输入要查找的值(输入-2跳出测试)：");int key = s.nextInt();if(key == -2) {break;}int index = search(arr, key);if (index == -1) {System.out.println(key + "未找到！");} else {System.out.println(key + "的索引是：" + index);}}}public static int search(int[] arr, int key) {//定义lowint low = 0;//定义highint high = arr.length;//定义中间位置midint mid = (low + high) / 2;//使用while循环进行判断while (low <= high) {//判断key是否与arr[mid]相等if (key == arr[mid]) {//找到key的对应索引并返回return mid;} else if (key > arr[mid]) {//更新low的值,往mid右侧寻找low = mid + 1;//更新mid的值mid = (low + high) / 2;} else {//更新high的值，往mid左侧寻找high = mid - 1;//更新mid的值mid = (low + high) / 2;}}//未找到返回-1return -1;}//使用冒泡排序法对数组进行从小到大的排序public static void sort(int[] arr) {for (int i = 0; i < arr.length; i++) {for (int j = i; j < arr.length; j++) {int temp;if (arr[i] > arr[j]) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}//打印排序后的数组System.out.println("排序后的数组为：");for (int k : arr) {System.out.print(k + "  ");}System.out.println();}}

运行截图为：
在这里插入图片描述

使用递归的代码为：
package Homework;

import java.util.Scanner;

/**
*

  • 内容： 二分法查找用递归
  • @author 陌意随影
  • @date:2019年7月10日下午9:48:51
    */

public class HomeWork18 {

public static void main(String[] args) {// 定义并初始化一个一维数组int[] arr = { 1, 13, 11, 6, 4, 9 };// 排序sort(arr);// 多次调试while (true) {Scanner s = new Scanner(System.in);System.out.println("请输入要查找的值(输入-2跳出测试)：");int key = s.nextInt();if (key == -2) {break;}int index = search(arr, key, 0, arr.length);if (index == -1) {System.out.println(key + "未找到！");} else {System.out.println(key + "的索引是：" + index);}}
}public static int search(int[] arr, int key, int low, int high) {// 定义中间位置midint mid = (low + high) / 2;// 使用while循环进行判断while (low <= high) {// 判断key是否与arr[mid]相等if (arr[mid] == key) {// 找到key的对应索引并返回return mid;}// 往左侧继续递归寻找else if (arr[mid] > key) {// 更新high的值，往mid左侧寻找high = mid - 1;// 递归寻找return search(arr, key, low, mid - 1);}// 往右侧继续递归寻找else {// 更新low的值,往mid右侧寻找low = mid + 1;// 递归寻找return search(arr, key, low, high);}}// 未找到返回-1return -1;
}// 使用冒泡排序法对数组进行从小到大的排序
public static void sort(int[] arr) {int temp;for (int i = 0; i < arr.length; i++) {for (int j = i; j < arr.length; j++) {if (arr[i] > arr[j]) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}// 打印排序后的数组System.out.println("排序后的数组为：");for (int k : arr) {System.out.print(k + "  ");}System.out.println();}

}
运行截图为：
在这里插入图片描述

这篇关于Java和c++中二分法查找数组元素的实现机制的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1073425。

相关文章

Java实现字节字符转bcd编码

Java实现字节字符转bcd编码

《Java实现字节字符转bcd编码》BCD是一种将十进制数字编码为二进制的表示方式,常用于数字显示和存储,本文将介绍如何在Java中实现字节字符转BCD码的过程,需要的小伙伴可以了解下... 目录前言BCD码是什么Java实现字节转bcd编码方法补充总结前言BCD码（Binary-Coded Decima
阅读更多...
SpringBoot全局域名替换的实现

SpringBoot全局域名替换的实现

《SpringBoot全局域名替换的实现》本文主要介绍了SpringBoot全局域名替换的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录 项目结构⚙️ 配置文件application.yml️ 配置类AppProperties.Ja
阅读更多...
Java使用Javassist动态生成HelloWorld类

Java使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC
阅读更多...
JavaScript中的高级调试方法全攻略指南

JavaScript中的高级调试方法全攻略指南

《JavaScript中的高级调试方法全攻略指南》什么是高级JavaScript调试技巧,它比console.log有何优势,如何使用断点调试定位问题,通过本文,我们将深入解答这些问题,带您从理论到实... 目录观点与案例结合观点1观点2观点3观点4观点5高级调试技巧详解实战案例断点调试：定位变量错误性能分
阅读更多...
Python实现批量CSV转Excel的高性能处理方案

Python实现批量CSV转Excel的高性能处理方案

《Python实现批量CSV转Excel的高性能处理方案》在日常办公中,我们经常需要将CSV格式的数据转换为Excel文件,本文将介绍一个基于Python的高性能解决方案,感兴趣的小伙伴可以跟随小编一... 目录一、场景需求二、技术方案三、核心代码四、批量处理方案五、性能优化六、使用示例完整代码七、小结一、
阅读更多...
Java实现将HTML文件与字符串转换为图片

Java实现将HTML文件与字符串转换为图片

《Java实现将HTML文件与字符串转换为图片》在Java开发中,我们经常会遇到将HTML内容转换为图片的需求,本文小编就来和大家详细讲讲如何使用FreeSpire.DocforJava库来实现这一功... 目录前言核心实现：html 转图片完整代码场景 1：转换本地 HTML 文件为图片场景 2：转换 H
阅读更多...
Java使用jar命令配置服务器端口的完整指南

Java使用jar命令配置服务器端口的完整指南

《Java使用jar命令配置服务器端口的完整指南》本文将详细介绍如何使用java-jar命令启动应用,并重点讲解如何配置服务器端口,同时提供一个实用的Web工具来简化这一过程,希望对大家有所帮助... 目录1. Java Jar文件简介1.1 什么是Jar文件1.2 创建可执行Jar文件2. 使用java
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
C#使用Spire.Doc for .NET实现HTML转Word的高效方案

C#使用Spire.Doc for .NET实现HTML转Word的高效方案

《C#使用Spire.Docfor.NET实现HTML转Word的高效方案》在Web开发中,HTML内容的生成与处理是高频需求,然而,当用户需要将HTML页面或动态生成的HTML字符串转换为Wor... 目录引言一、html转Word的典型场景与挑战二、用 Spire.Doc 实现 HTML 转 Word1
阅读更多...
C#实现一键批量合并PDF文档

C#实现一键批量合并PDF文档

《C#实现一键批量合并PDF文档》这篇文章主要为大家详细介绍了如何使用C#实现一键批量合并PDF文档功能,文中的示例代码简洁易懂,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言效果展示功能实现1、添加文件2、文件分组（书签）3、定义页码范围4、自定义显示5、定义页面尺寸6、PDF批量合并7、其他方法
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2