做外贸用什么网站好,搭建企业网站,齐装网,仿美团外卖小程序源码二分查找#xff08;Binary Search#xff09;是一种高效的搜索算法#xff0c;适用于已排序的数组或列表。通过每次将搜索范围减半#xff0c;其时间复杂度为 O(log n)#xff0c;远优于线性查找的 O(n)。快速理解二分查找#xff08;也叫折半查找#xff09;的思路特别…二分查找Binary Search是一种高效的搜索算法适用于已排序的数组或列表。通过每次将搜索范围减半其时间复杂度为O(log n)远优于线性查找的O(n)。快速理解二分查找也叫折半查找的思路特别像我们玩 “猜数字” 游戏比如猜 1~100 之间的数字你先猜 50对方说 “大了”那你就知道答案在 1~49 之间再猜 25对方说 “小了”就知道答案在 26~49 之间每次都把查找范围缩小一半直到找到目标值或确定目标值不存在。因此只要你的数据是有序的二分查找就是最高效的选择。算法核心思想确定搜索范围初始化左边界left为 0右边界right为数组长度减 1。计算中间索引取中间位置mid left (right - left) // 2避免整数溢出。比较目标值若arr[mid] target返回mid。若arr[mid] target缩小范围至右半部分left mid 1。若arr[mid] target缩小范围至左半部分right mid - 1。终止条件left right当left right时说明目标不存在返回-1.代码实现(基础版javaclass Solution { // 准备一个无序数组先排序二分查找必须用有序数组 public int search(int[] nums, int target) { // 1. 初始化左右边界 int left 0,right nums.length - 1; // 2. 循环查找 while(leftright){ // 计算中间索引避免溢出 int mid (right left)/2 ; int num nums[mid]; if(num target) { // 找到目标返回索引 return mid; }else if(target num){ // 目标在右半区左边界右移 left mid 1; }else { // 目标在左半区右边界左移 right mid - 1; } } // 没找到返回-1 return -1; } }提醒tips必须先排序二分查找的前提是数组有序。如果数组是乱的比如[5,2,9]直接用二分查找会得到错误结果。一定要先用Arrays.sort()把数组排好序。mid 的计算方式不要写成mid (left right) / 2当left和right都是很大的数时会导致整数溢出。正确写法是mid left (right - left) / 2。边界更新要加 1 / 减 1不要写成left mid或right mid这会导致死循环。因为如果arr[mid]不是目标值这个位置就可以排除所以要直接跳到mid 1或mid - 1。循环条件是left right如果写成left right会漏掉最后一个可能的元素。比如当left和right相等时mid就是这个元素不判断就会错过总结基础版应对大多数情况下一下步骤完全可以直接套用初始化边界左指针left0右指针right数组长度-1循环查找当left right时有查找空间计算中间索引mid left (right-left)/2避免整数溢出替代(leftright)/2比较缩范围arr[mid] target找到目标返回midarr[mid] target目标在右半区left mid 1arr[mid] target目标在左半区right mid - 1未找到循环结束无返回返回-1表示目标不存在。