使用二分查找的前提条件:
-
有序(单调递增或递减)
-
存在边界
-
能够通过索引访问
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法,前提是数据结构必须先排好序,可以在数据规模的对数时间复杂度内完成查找。但是,二分查找要求线性表具有有随机访问的特点(例如数组),也要求线性表能够根据中间元素的特点推测它两侧元素的性质,以达到缩减问题规模的效果。
代码模板:
public int sort(int[] nums, int target){
int left = 0;
int right = nums.length-1;
while(left < right){
int mid = (left+right)/2;
if(nums[mid] == target ){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
例题1:
LeetCode ——69.x的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4 输出: 2 示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
class Solution {
public int mySqrt(int x) {
if (x==0 || x==1) return x;
int left = 0;
int right = x/2+1;
int res = 0;
while(left <= right){
int mid = (left + right)/2;
if(mid == x/mid){
return mid;
}else if(mid < x/mid){ //取小,防止过大
left = mid +1;
res = mid;
}else{
right = mid -1;
}
}
return res;
}
}
例题2:
剑指offer 53 - II 0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例 1:
输入: [0,1,3] 输出: 2 示例 2:
输入: [0,1,2,3,4,5,6,7,9] 输出: 8
解法一:个人套模板解法
class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
if(len == 1) return nums[0]==0 ?1:0;
if(nums[len-1]== len-1) return len;
if(nums[0]!=0) return 0;
int left = 0;
int right = len -1;
int mid = 0;
while(left <= right){
mid = (left + right)/2;
if(nums[mid]>mid && nums[mid-1]==mid-1){
return mid;
}else if(nums[mid] == mid ){
left = mid + 1;
}else if(nums[mid]>mid){
right = mid - 1;
}
}
return mid;
}
}
执行结果:(内存消耗更少)
解法2:网上大佬的解法(代码更简洁)
class Solution {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length-1;
int mid = 0;
while(left <= right){
mid = (left + right)/2;
if(nums[mid] == mid) left = mid +1;
else right = mid -1;
}
return left;
}
}
执行结果:
以上是我个人学习总结的笔记,当然目前还是还是不够的,对于二分法的理解还要多刷题,多思考,多理解!
评论