C#.NET实现二分查找
2021/9/29 12:10:45
本文主要是介绍C#.NET实现二分查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
定义:
二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
适用范围:
当数据量很大并且有序时,适宜采用该方法。
基本思想:
假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较,
如果当前位置arr[k] 值等于key,则查找成功;
若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low, mid - 1];
若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid + 1, high],
直到找到为止,时间复杂度:O(log(n))
算法难点:
对边界条件细节掌握,也就是区间状态。区间状态基本为下边两种。
若是区间为[left, right]既while(left<=arr.Length-):更新状态方式left = mid + 1; right = mid - 1;
若是区间为[left, right)既while(left<arr.Length):更新状态方式left = mid + 1; right = mid;
代码实现:
该代码是实现区间为[left,right]的。
public static int BinarySearch(int[] nums, int target) { // 避免当 target不存在与数组,多次进行循环运算 if (target < nums[0] || target > nums[nums.Length - 1]) { return -1; } int left = 0, right = nums.Length - 1; while (left <= right) { int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; }
力扣题目
- 二分查找:https://leetcode-cn.com/problems/binary-search/
- 二分法题库 https://leetcode-cn.com/tag/binary-search/problemset/
这篇关于C#.NET实现二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2022-03-01沐雪多租宝商城源码从.NetCore3.1升级到.Net6的步骤
- 2024-12-06使用Microsoft.Extensions.AI在.NET中生成嵌入向量
- 2024-11-18微软研究:RAG系统的四个层次提升理解与回答能力
- 2024-11-15C#中怎么从PEM格式的证书中提取公钥?-icode9专业技术文章分享
- 2024-11-14云架构设计——如何用diagrams.net绘制专业的AWS架构图?
- 2024-05-08首个适配Visual Studio平台的国产智能编程助手CodeGeeX正式上线!C#程序员必备效率神器!
- 2024-03-30C#设计模式之十六迭代器模式(Iterator Pattern)【行为型】
- 2024-03-29c# datetime tryparse
- 2024-02-21list find index c#
- 2024-01-24convert toint32 c#