二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
当数据量很大并且有序时,适宜采用该方法。
假设数据是按升序排序的,对于给定值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; }