题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
简要描述二分法
首先应为一个有序数列，我们将会数字设定为一个数组nums，将要在数组中寻找的目标设置为target。在数组中，对数组中间值nums[middle]与target进行判断，并对其进行空间的压缩，然后再次判断新的nums[middle]与target的大小关系，直到nums[middle]与target相等为止
思路
- 首先明确题目要求，为寻找目标值，若存在返回下标，不存在则返回-1，标准的二分查找
- 明确了二分查找要求后，确定使用左闭右闭还是左闭合又开，即选择[left,right]还是[left,right)，这里我选择的是左闭右闭
- 确定了使用左闭右闭写法之后，便应该明确怎么写代码。由于目标值在[left,right]区间，所以while(left ? right)中？处应填写<= ,因为在[left,right]区间中,left == right是存在的，例[1,1]，所以应当使用<=
- 同时判断语句if (nums[middle] > target) 时,由于middle大于目标值，所以即目标值出现在左半边，所以应当将right(即右边界)赋值为middle - 1，因为判断条件为if (nums[middle] > target)，此时的nums[middle] 必然不是目标值，所以可以自然往左一位
- 而判断语句if (nums[middle] < target)时，由于middle小于目标值，所以即目标值出现在右半边，所以应当将left(即左边界)赋值为middle + 1，原因参考上一点
- 当nums[middle] = tarage 时，直接return middle输出结果即可
- 最后在while循环外写入return -1表示目标值不存在即可
代码
class Solution {
public int search(int[] nums, int target) {
int left = 0 ;
int right = nums.length -1;
while(left <= right){
int middle = left + (right - left) / 2;
if(nums[middle] > target)
right = middle -1;
else if(nums[middle] < target)
left = middle + 1;
else if(nums[middle] == target)
return middle;
}
return -1;
}
}
提交截图
