首页 > Windows开发 > 详细

C#.NET实现二分查找

时间:2022-05-27 19:29:47      阅读:2      评论:0      收藏:0      [点我收藏+]

定义:

二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。

适用范围:

当数据量很大并且有序时,适宜采用该方法。

基本思想:

假设数据是按升序排序的,对于给定值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实现二分查找

原文:https://www.cnblogs.com/Z7TS/p/15352191.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!