二分法题目:在有序数组中A内,查找数组中的某一个元素的下标(本题是从由小到大的顺序)

本文主要是介绍二分法题目:在有序数组中A内,查找数组中的某一个元素的下标(本题是从由小到大的顺序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二分查找算法,也称为折半查找算法,是一种在有序数组中查找特定元素的高效算法。它的基本思想是将查找的区间逐渐缩小,直到找到目标元素或者确定目标元素不存在。

算法步骤如下:

  1. 初始化:首先,确定数组的左右边界,通常初始时左边界为数组的起始索引,右边界为数组的末尾索引。

  2. 找到中间元素:计算左右边界的中间索引,然后取得该索引处的元素值。

  3. 比较中间元素

    • 如果中间元素等于目标值,查找成功,返回元素索引。
    • 如果中间元素大于目标值,说明目标值应该在左半边,将右边界移动到中间索引的左边一位。
    • 如果中间元素小于目标值,说明目标值应该在右半边,将左边界移动到中间索引的右边一位。
  4. 重复:在新的查找区间中,重复步骤2和步骤3,直到左边界大于右边界,此时查找失败,返回-1,或者返回指示元素不存在的其他值。

算法特点

  • 二分查找算法的时间复杂度是O(log n),其中n是数组的大小。这是因为每一次比较都将查找范围缩小为原来的一半。

  • 但是,二分查找算法要求输入的数据必须是有序的。如果数组无序,需要事先进行排序操作。

  • 由于二分查找每次将查找范围缩小为一半,因此它的效率非常高,尤其是在大型数据集中的查找操作。

  • 二分查找算法是一种迭代的算法,也可以使用递归实现。

Java版:

package LeetCode_1.Binary_search;
//小淼的算法之路//二分法题目:在有序数组中A内,查找数组中的某一个元素的下标(本题是从由小到大的顺序)public class Binary_search {//二分查找算法版本1.0public static int BinarySearchBasic(int[] a, int target){int i = 0,j = a.length -1;//设置指针和初值while (i <= j){int m = (i + j)>>>1;//m:中间值if(target < a[m]){//若查找的在中间值左边(小于中间值),最大值指针j占据中间值-1的位置,在进行计算j = m -1;} else if (a[m] < target){//若查找的在中间值右边(大于中间值),最小值指针j占据中间值+1的位置,在进行计算i = m + 1;} else {return m;//否则就是target值与中间值相等,直接返回中间值}}return -1;//不存在时返回-1,因为能找到的都在数组当中,在数组中的都有一个索引值,所以能找到的输出的数组索引值不可能为-1}/*本题问题1:为什么i<=j 意味着区间未比较的元素,而不是i<j  ?*       答:因为i,j 它们指向的元素也会参与比较,若i<j,则参与比较的只能是i与j中间的值,若这时i与j指向的元素相同则该算法会发生错误。* 本题问题2:为什么int m = (i + j)>>>1;,而不是int m = (i + j) / 2;  ?*       答:如果使用int m = (i + j) / 2 来确定中间值的话多次循环会有问题:这与二进制的第一位是不是符号位有关(1:负,0:正)。*           然而int m = (i + j)>>>1 这种方式:将i+j表示成的二进制整体向右移动一位(二进制对应的十进制做/2操作)* *///二分查找算法版本2.0public static int BinarySearchUpgrades(int[] a, int target){int i = 0,j = a.length;         //第一处改动while (i < j){                  //第二处改动int m = (i + j)>>>1;if(target < a[m]){j = m;                  //第三处改动} else if (a[m] < target){i = m + 1;} else {return m;}}return -1;}//测试类public static void main(String[] args) {int[] a = {7,13,21,30,38,44,52,53,78,79,88,89,91,92,93,94};int target = 92;long startTime = System.nanoTime();;//开始时时间点int result = BinarySearchBasic(a, target);//执行的算法long endTime = System.nanoTime();//结束时时间点long elapsedTime = endTime - startTime;//算法占用时间if (result != -1) {System.out.println("二分查找法1.0版本----------"+"目标值 " + target + " 在数组中的索引是 " + result+"\n"+"算法执行时间(纳秒): " + elapsedTime);} else {System.out.println("二分查找法1.0版本----------"+"目标值 " + target + " 未在数组中找到");}long startTime_1 = System.nanoTime();;//开始时时间点int result_1 = BinarySearchUpgrades(a, target);long endTime_1 = System.nanoTime();//结束时时间点long elapsedTime_1 = endTime_1 - startTime_1;//算法占用时间if (result_1 != -1) {System.out.println("二分查找法2.0版本----------"+"目标值 " + target + " 在数组中的索引是 " + result_1+"\n"+"算法执行时间(纳秒): " + elapsedTime_1);} else {System.out.println("二分查找法2.0版本----------"+"目标值 " + target + " 未在数组中找到");}}
}

JavaScript:

function binarySearchBasic(a, target) {let i = 0, j = a.length - 1; // 设置指针和初值while (i <= j) {let m = (i + j) >>> 1; // m:中间值if (target < a[m]) {// 若查找的在中间值左边(小于中间值),最大值指针j占据中间值-1的位置,在进行计算j = m - 1;} else if (a[m] < target) {// 若查找的在中间值右边(大于中间值),最小值指针j占据中间值+1的位置,在进行计算i = m + 1;} else {return m; // 否则就是target值与中间值相等,直接返回中间值}}return -1; // 不存在时返回-1,因为能找到的都在数组当中,在数组中的都有一个索引值,所以能找到的输出的数组索引值不可能为-1
}function binarySearchUpgrades(a, target) {let i = 0, j = a.length; // 第一处改动while (i < j) { // 第二处改动let m = (i + j) >>> 1;if (target < a[m]) {j = m; // 第三处改动} else if (a[m] < target) {i = m + 1;} else {return m;}}return -1;
}const a = [7, 13, 21, 30, 38, 44, 52, 53, 78, 79, 88, 89, 91, 92, 93, 94];
const target = 92;let startTime = performance.now(); // 开始时时间点
let result = binarySearchBasic(a, target);
let endTime = performance.now(); // 结束时时间点
let elapsedTime = endTime - startTime; // 算法占用时间if (result !== -1) {console.log(`二分查找法1.0版本---------- 目标值 ${target} 在数组中的索引是 ${result}\n算法执行时间(毫秒): ${elapsedTime}`);
} else {console.log(`二分查找法1.0版本---------- 目标值 ${target} 未在数组中找到`);
}let startTime1 = performance.now(); // 开始时时间点
let result1 = binarySearchUpgrades(a, target);
let endTime1 = performance.now(); // 结束时时间点
let elapsedTime1 = endTime1 - startTime1; // 算法占用时间if (result1 !== -1) {console.log(`二分查找法2.0版本---------- 目标值 ${target} 在数组中的索引是 ${result1}\n算法执行时间(毫秒): ${elapsedTime1}`);
} else {console.log(`二分查找法2.0版本---------- 目标值 ${target} 未在数组中找到`);
}

这篇关于二分法题目:在有序数组中A内,查找数组中的某一个元素的下标(本题是从由小到大的顺序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/280510

相关文章

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

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

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

C++ Primer 多维数组的使用

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