使用条件
- 有序数组
- 元素不重复
区间设置
- 左闭右闭：
- 左右区间边界都要在数组的索引有效范围内（left=0,right=数组长度-1）
- 判断条件 left(左边界)<=right(右边界)
- 左闭右开
- 左区间边界在数组的有效索引范围内，右边界不在（left=0,right=数组长度)
- 判断条件 left(左边界)<right(右边界)
例题
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
- 有序数组
- 数组没有重复元素
//左闭右闭
public int search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int n=left+(right-left)/2;
if(target>nums[n]){
left=n+1;//当前元素的值不满足，缩小区间
}else if(target<nums[n]){
right=n-1;
}else{
return n;
}
}
return -1;
}
//左闭右开
public int search(int[] nums, int target) {
int left=0;
int right=nums.length;//不包含右边界
while(left<right){//left==right不成立
int n=left+(right-left)/2;
if(target>nums[n]){
left=n+1;
}else if(target<nums[n]){
right=n;//索引检查始终不包含右边界
}else{
return n;
}
}
return -1;
}
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
- 有序数组
- 数组没有重复元素
//左闭右闭
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int n=left+(right -left)/2;
if(target>nums[n])
{
left=n+1;
}else if(target<nums[n]){
right=n-1;
}else{
return n;
}
}
return left;//没有查到，当left-1=right时退出循环
}
//左闭右开
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length;//不包含右边界
while(left<right){//left==right不成立
int n=left+(right -left)/2;
if(target>nums[n])
{
left=n+1;
}else if(target<nums[n]){
right=n;
}else{
return n;
}
}
return left;
}
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（Leetcode）
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
- 数组有序
//二分查找对应元素的左右边界
public int[] searchRange(int[] nums, int target) {
int left=searchRangeLeft(nums,target);
int right=searchRangeRight(nums,target);
if(right==-2||left==-2)return new int[]{-1,-1};//target的值比数组最大值大或最小值小
if(right-left>1)return new int[]{left,right};//target存在在数组中，且因为返回值是边界
// 元素不存在
return new int[]{-1,-1};
}
//缩小右边界去找左边界
public int searchRangeLeft(int[] nums, int target){
int left=0;
int right=nums.length-1;
int leftBro=-2;
while(left<=right){
int n=left+(right-left)/2;
if(target<=nums[n]){
right=n-1;
leftBro=right;//当target==nums[n]时更新
}else{
left=n+1;
}
}
return leftBro;
}
//缩小左边界去找右右边界
public int searchRangeRight(int[] nums, int target){
int left=0;
int right=nums.length-1;
int rightBro=-2;
while(left<=right){
int n=left+(right-left)/2;
if(target>=nums[n]){
left=n+1;
rightBro=left;
}else{
right=n-1;
}
}
return rightBro;
}
/*****************************************************/
//二分查找要查找的元素，在从查找的元素位置向两侧查找
public int[] searchRange(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int n=left+(right-left)/2;
if(target>nums[n]){
left=n+1;
}else if(target<nums[n]){
right=n-1;
}else{//查找到当前元素，开始查找边界
while(left<=n&&nums[left]!=target){
left++;
}
while(right>=n&&nums[right]!=target){
right--;
}
return new int []{left,right};
}
}
return new int[]{-1,-1};
}
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
- 将整数近似为右边界
public int mySqrt(int x) {
int i=0;
int j=x;
int ans=-1;
if(x==0)return 0;
if(x==1)return 1;//防止n为0的情况
while(i<=j){
int n=i+(j-i)/2;
if(x/n<n){//防止溢出
j=n-1;
}else{
i=n+1;
ans=n;
/*只要mid <= x/mid，left左边界就会一直向右移动，ans就会一直更新（变大），直到不在满足mid <= x/mid 的条件为止，ans就会停止更新，永远停在满足mid<=x/mid条件下面的最后一次更新，即满足ans * ans <= mid的最大值*/
}
}
return ans;
}