二分法题目：在有序数组中A内，查找数组中的某一个元素的下标（本题是从由小到大的顺序）

2023-10-25 06:04
文章标签 数组 题目 元素 查找 有序 顺序 二分法 下标 是从 由小到大 本题

本文主要是介绍二分法题目：在有序数组中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。

相关文章

hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...
题目1380：lucky number

题目1380：lucky number

题目1380：lucky number 时间限制：3 秒 内存限制：3 兆 特殊判题：否 提交：2839 解决：300 题目描述： 每个人有自己的lucky number，小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话，都是他的lucky number。但是，现在这个序列很大，他无法快速找到所有lucky number。既然
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
遮罩，在指定元素上进行遮罩

遮罩，在指定元素上进行遮罩

废话不多说，直接上代码： ps:依赖 jquer.js 1.首先，定义一个 Overlay.js  代码如下： /*遮罩 Overlay js 对象*/function Overlay(options){//{targetId:'',viewHtml:'',viewWidth:'',viewHeight:''}try{this.state=false;//遮罩状态 true 激活，f
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配（Exact Match）2. 正则表达式匹配（Regex Match）3. 前缀匹配（Prefix Match） 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中，location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求，NGINX 提供了多种匹
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2