当前位置：首页 > news >正文

LeetCode 704 二分查找 Java

news 2025/6/14 8:03:38

1.确定区间的定义

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

左闭右闭，边界值都能取到，左闭右开，左边界可以取到，右边界取不到

先放代码,相关的描述放在代码里了

class Solution {public int search(int[] nums, int target) {//左闭右闭区间//int left=0,right=nums.length-1;// while(left<=right){//     int mid=left+(right-left)/2;//     if(nums[mid]==target){//         return mid;//     }//     else if(nums[mid]<target){//         left=mid+1;//     }//     else if(nums[mid]>target){//         right=mid-1;//     }// }// return -1;//左闭右开区间int left=0,right=nums.length;while(left<right){int mid=left+(right-left)/2;if(nums[mid]==target){return mid;}else if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid;}}return -1;}
}

2.左闭右闭区间 [left, right]

   左闭右闭区间int left=0,right=nums.length-1;//右边界是可以取到的，所以不能为nums.length,这实际超出了数组长度while(left<=right){//左右边界可以相等，举个例子[1,1],这是正确的int mid=left+(right-left)/2;if(nums[mid]==target){return mid;}else if(nums[mid]<target){left=mid+1;//左边界可以取到，这里排除了mid，所以左边界取mid+1}else if(nums[mid]>target){right=mid-1;//与上面同理}}return -1;

3.左闭右开区间 [left, right)

//左闭右开区间int left=0,right=nums.length;//右边界取不到，这里可以为nums.lengthwhile(left<right){//左边界能取到，右边界取不到，所以左右边界不能相同，例如[1,1)是不对的int mid=left+(right-left)/2;if(nums[mid]==target){return mid;}else if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid;//右边界取不到，排除了mid之后，可以让右边界等于mid}}return -1;