Java算法篇之二分查找模板
大家好,这里是教授.F
模板一:
用于查找可以通过访问数组中的 单个索引 来确定的元素或条件。
对于二分查找,我认为最适用在通过一个范围确定某一点。 就是通过折中的方式来逼近到某一个点。
有很多场景可以使用它,比如:求出一个值的平方根,我们可以通过使用折中的方式不断逼近,以达到目的。
int binarySearch(int[] nums, int target){if(nums == null || nums.length == 0)return -1;int left = 0, right = nums.length - 1;while(left <= right){//这里有等号// Prevent (left + right) overflowint mid = left + (right - left) / 2;if(nums[mid] == target){ return mid; }else if(nums[mid] < target) { left = mid + 1; }else { right = mid - 1; }}// End Condition: left > rightreturn -1;
}
模板二:
它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
int binarySearch(int[] nums, int target){if(nums == null || nums.length == 0)return -1;int left = 0, right = nums.length;while(left < right){// Prevent (left + right) overflowint mid = left + (right - left) / 2;if(nums[mid] == target){ return mid; }else if(nums[mid] < target) { left = mid + 1; }else { right = mid; }}// Post-processing:// End Condition: left == rightif(left != nums.length && nums[left] == target) return left;return -1;
}