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中ArrayList和LinkedList有什么区别举例详解

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》：本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程
阅读更多...
JavaScript中的reduce方法执行过程、使用场景及进阶用法

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》：本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
Java调用DeepSeek API的最佳实践及详细代码示例

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》：本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.
阅读更多...
Spring AI集成DeepSeek的详细步骤

Spring AI集成DeepSeek的详细步骤

《SpringAI集成DeepSeek的详细步骤》DeepSeek作为一款卓越的国产AI模型,越来越多的公司考虑在自己的应用中集成,对于Java应用来说,我们可以借助SpringAI集成DeepSe... 目录DeepSeek 介绍Spring AI 是什么？1、环境准备2、构建项目2.1、pom依赖2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
Spring Cloud LoadBalancer 负载均衡详解

Spring Cloud LoadBalancer 负载均衡详解

《SpringCloudLoadBalancer负载均衡详解》本文介绍了如何在SpringCloud中使用SpringCloudLoadBalancer实现客户端负载均衡,并详细讲解了轮询策略和... 目录1. 在 idea 上运行多个服务2. 问题引入3. 负载均衡4. Spring Cloud Load
阅读更多...
Springboot中分析SQL性能的两种方式详解

Springboot中分析SQL性能的两种方式详解

《Springboot中分析SQL性能的两种方式详解》文章介绍了SQL性能分析的两种方式：MyBatis-Plus性能分析插件和p6spy框架,MyBatis-Plus插件配置简单,适用于开发和测试环... 目录SQL性能分析的两种方式:功能介绍实现方式:实现步骤:SQL性能分析的两种方式:功能介绍记录
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2