二分查找与搜索算法

二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

/* 二分查找（双闭区间） */intbinarySearch(int[]nums,inttarget){// 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素inti=0,j=nums.length-1;// 循环，当搜索区间为空时跳出（当 i > j 时为空）while(i<=j){intm=i+(j-i)/2;// 计算中点索引 mif(nums[m]<target)// 此情况说明 target 在区间 [m+1, j] 中i=m+1;elseif(nums[m]>target)// 此情况说明 target 在区间 [i, m-1] 中j=m-1;else// 找到目标元素，返回其索引returnm;}// 未找到目标元素，返回 -1return-1;}

在算法题中，我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索“和”为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。这是算法第一题两数之和。
1，暴力枚举

/* 方法一：暴力枚举 */int[]twoSumBruteForce(int[]nums,inttarget){intsize=nums.length;// 两层循环，时间复杂度为 O(n^2)for(inti=0;i<size-1;i++){for(intj=i+1;j<size;j++){if(nums[i]+nums[j]==target)returnnewint[]{i,j};}}returnnewint[0];}

2，哈希查找，借助一个哈希表，键值对分别为数组元素和元素索引。循环遍历数组。

/* 方法二：辅助哈希表 */int[]twoSumHashTable(int[]nums,inttarget){intsize=nums.length;// 辅助哈希表，空间复杂度为 O(n)Map<Integer,Integer>dic=newHashMap<>();// 单层循环，时间复杂度为 O(n)for(inti=0;i<size;i++){if(dic.containsKey(target-nums[i])){returnnewint[]{dic.get(target-nums[i]),i};}dic.put(nums[i],i);}returnnewint[0];}

线性搜索适用于小型或频繁更新的数据；二分查找适用于大型、排序的数据；哈希查找适用于对查询效率要求较高且无须范围查询的数据；树查找适用于需要维护顺序和支持范围查询的大型动态数据。用哈希查找替换线性查找是一种常用的优化运行时间的策略，可降低时间复杂度。