Net Core教程

C#.NET实现二分查找

本文主要是介绍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;
        }

力扣题目

  1. 二分查找:https://leetcode-cn.com/problems/binary-search/
  2. 二分法题库 https://leetcode-cn.com/tag/binary-search/problemset/
这篇关于C#.NET实现二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!