网站建设读书笔记,网页商城设计商城网站设计案例,网站几个数据库,搜索引擎调词工具目录 1. 二分查找概述2. 精确查找2.1 【left#xff0c;right】2. 2 【left#xff0c;right#xff09; 3. 范围查找总结 1. 二分查找概述 二分查找法#xff0c;也称为二分搜索法或折半查找法#xff0c;是一种在有序数组中查找特定元素的搜索算法。其基本思想是#x… 目录 1. 二分查找概述2. 精确查找2.1 【leftright】2. 2 【leftright 3. 范围查找总结 1. 二分查找概述 二分查找法也称为二分搜索法或折半查找法是一种在有序数组中查找特定元素的搜索算法。其基本思想是通过不断将待查找的区间分成两半并与待查找的元素进行比较根据比较结果调整查找区间直到找到元素或区间被缩小至0为止。时间复杂度为O(log n)
使用条件二分查找要求数组必须是有序的无论是升序还是降序。如果数组无序则需要先进行排序操作。易错点while循环过程中left与right的关系容易错乱left与right指针的移动容易错。查找情况二分查找最常见的就是查找某一个序列中存在的精确值target然而还有一部分是利用二分查找来进行范围划分。
2. 精确查找 为了捋清楚终止条件与指针移动如何确定需要先从搜索定义区间入手搜索区间可以分为【leftright】和【leftright。
2.1 【leftright】
当搜索区间为【leftright】时说明二分查找过程中每次搜索区间应该均需要满足该定义。此时二分查找步骤为
确定查找区间设数组为arr查找范围为[left, right]初始时left0rightn-1其中n为数组arr的长度。确定循环条件由于区间是左闭右闭所以left right符合定义区间因此搜索过程中应当满足的条件为whileleft right计算中间位置mid (left right) / 2注意为了避免整数相加导致的整数溢出问题有时也使用mid left (right - left) / 2的计算方式。比较中间元素与目标值 如果arr[mid]等于目标值则查找成功返回mid。如果arr[mid]大于目标值则说明目标值在左半部分且arr[mid]将不会再需要处于搜索区间内了因为arr[mid]已经一定不等于target了则将查找范围更新为[left, mid-1]right mid - 1。 如果arr[mid]小于目标值则说明目标值在右半部分,且arr[mid]将不会再需要处于搜索区间内了因为arr[mid]已经一定不等于target了将查找范围更新为[mid1, right]left mid 1。重复步骤2和步骤3直到找到目标值或查找范围为空即left right如果查找范围为空则说明目标值不存在于数组中。
public static int binarySearch(int[] arr, int target) { int left 0; int right arr.length - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出同时更准确地找到中间位置 if (arr[mid] target) { return mid; // 找到目标元素返回索引 } else if (arr[mid] target) { left mid 1; // 目标元素在右半部分 } else { right mid - 1; // 目标元素在左半部分 } } // 未找到目标元素返回-1 return -1; } 2. 2 【leftright
当搜索区间为【leftright时
确定查找区间设数组为arr查找范围为[left, right初始时left0rightn其中n为数组arr的长度。确定循环条件由于区间是左闭右开所以left ! right符合定义区间因此搜索过程中应当满足的条件为whileleft right计算中间位置mid (left right) / 2注意为了避免整数除法导致的精度问题有时也使用mid left (right - left) / 2的计算方式。比较中间元素与目标值 如果arr[mid]等于目标值则查找成功返回mid。如果arr[mid]大于目标值则说明目标值在左半部分arr[mid]将不会再需要处于搜索区间内了因为arr[mid]已经一定不等于target了,并且right一直不在搜索范围内所以将查找范围更新为[left, mid)right mid。 如果arr[mid]小于目标值则说明目标值在右半部分,且arr[mid]将不会再需要处于搜索区间内了因为arr[mid]已经一定不等于target了但是left必须在搜索区间内所以将查找范围更新为[mid1, right]left mid 1。重复步骤2和步骤3直到找到目标值或查找范围为空即left right如果查找范围为空则说明目标值不存在于数组中。
public static int binarySearch(int[] arr, int target) { int left 0; int right arr.length; while (left right) { int mid left (right - left) / 2; // 防止溢出同时更准确地找到中间位置 if (arr[mid] target) { return mid; // 找到目标元素返回索引 } else if (arr[mid] target) { left mid 1; // 目标元素在右半部分 } else { right mid; // 目标元素在左半部分 } } // 未找到目标元素返回-1 return -1; } 3. 范围查找 有些时候target不一定存在于序列中但是我们想要得到大于target的序列区间小于等于target的序列区间 或者 大于等于target的序列区间小于target的序列区间。为了便于讨论下面将循环条件定义为whileleft right指针移动方向为right mid - 1left mid 1。 由于定义区间为【leftright】left right搜索到最后left肯定会等于right此时mid left right下一次移动后将不满足循环条件退出。最后一次是left移动还是right移动将直接影响最终查找的范围即等于号归left区间还是right区间。假设代码如下:
while(left right){int mid left (right - left)/2;if(nums[mid] target){//这里需要重点考虑如果有等号存在则说明如果mid所指就是target则哪个指针继续跳一个单位它就必不会等于mid对应的区间中也就不会出现等于taget的情况//区间【leftn】所指向的值均 target区间【0right】所指向的值均 targetright mid 1;}else{left mid - 1;}
}
return left;可以自行验证如果target不在序列中最终left将指向第一个大于target的元素right将指向最后一个小于target的元素。举例如下:
假设序列{.....2,3,4,5.......} target 3.5mid left right指向4
此时target小于mid之后执行right mid - 1right指向3left仍指向4。
nums[【leftn】 ] target , nums[ 【0right】 ] target假设序列{.....2,3,4,5.......} target 4.5mid left right指向4
此时target大于mid之后执行left mid 1left指向5right仍指向4
依然是nums[【leftn】 ] target , nums[ 【0right】 ] target如果target存在于序列中则最后执行right mid - 1还是left mid 1将会影响target放入哪一个区间中。如果target存在于序列中则mid最后所指就是target所以最后一次移动指针之前mid left right所指向的值就是target此时哪个指针继续跳一个单位它就必不会再有机会等于mid等于target所以其对应的区间中也就不会出现等于taget的情况。 因此上述 if 判断条件中的等号是否存在决定了是right指针会向左移动一格此时区间【leftn】所指向的值均 target区间【0right】所指向的值均 target还是left指针向右移动一格此时区间【leftn】所指向的值均 target区间【0right】所指向的值均 target
while(left right){int mid left (right - left)/2;if(nums[mid] target){//区间【leftn】所指向的值均 target区间【0right】所指向的值均 targetright mid 1;}else{left mid - 1;}
}
return left;总结
left指向第一个符合if中判断条件的元素right指向最后一个不符合if中判断条件的元素
当判断条件为if(nums[mid] target)时最终nums[【leftn】 ] target , nums[ 【0right】 ] target;当判断条件为if(nums[mid] target)时最终nums[【leftn】 ] target , nums[ 【0right】 ] target;
这种范围查找也非常适合在遇到元素重复出现需要找到重复元素的第一个元素或者重复元素的最后一个的位置索引。
