二分算法技巧

  1. 代码模板
1
2
3
4
5
6
7
8
9
10
11
12
13
while(left <= right){
	int mid = left + (right - left) / 2;
	if(arr[left] == target){
		return mid;
	}
	if(arr[mid] < target){
		left = mid + 1;
	}
	if(arr[mid] > target){
		right = mid - 1; 
	}
}
return left;

  1. 如果target值有多个

    1. 取最左边的值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    while(left <= right){
    	int mid = left + (right - left) / 2;
    	if(arr[mid] < target){
    		left = mid + 1;
    	}else{
    		right = mid - 1; 
    	}
    }
    return left;
    1. 取最右边的值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    while(left <= right){
      int mid = left + (right - left) / 2;
      if(arr[mid] <= target){
        left = mid + 1;
      }else{
        right = mid - 1; 
      }
    }
    return right;

  2. 取最靠近target的两边的第一个值

1
2
3
4
5
6
7
8
9
10
11
12
while(left <= right){
  int mid = left + (right - left) / 2;
  if(arr[mid] < target){
    left = mid + 1;
  }else{
    right = mid - 1; 
  }
}
// 如果取左边（注意相反的）
return right;
// 如果取右边（注意相反的）
return left;
  1. 查找峰值
1
2
3
4
5
6
7
8
9
10
11
12
13
// 这里不能相等，因为如果left == right时，刚好nums[mid] == nums[mid + 1]，那么会陷入死循环
while(left < right){
  int mid = left + (right - left) / 2;
  if(arr[mid] < arr[mid+1]){
  	// 说明峰值在mid+1~right之间，不包含mid
    left = mid + 1;
  }else{
  	//说明峰值在left～mid之间，是包含mid的，所以这里不应该-1
    right = mid; 
  }
}
// 返回left或right都行
return left;