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。

相关文章

一文详解如何在idea中快速搭建一个Spring Boot项目

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
OpenCV实现实时颜色检测的示例

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间
阅读更多...
Java对异常的认识与异常的处理小结

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。（1）简单定义-什么是
阅读更多...
SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一：基础配置（直接关闭目标路径日志）方案二：结合 Spring Profile 按环境屏蔽关
阅读更多...
Python实现精准提取 PDF中的文本,表格与图片

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容：获取整页文本与指定区域内容获取页面上的所有文本内容获取
阅读更多...
基于Python实现一个Windows Tree命令工具

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一：创建批处理文件并添加到PATH1
阅读更多...
Java使用HttpClient实现图片下载与本地保存功能

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2