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实现二分查找

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