[leetcode]704.二分查找-简单

704. 二分查找

题目：给定n个元素升序的整形数组nums和一个目标值target

要求：写一个搜索函数搜索整形数组nums中的target，如果目标值存在则返回下标，否则返回-1.。

Class Solution{
    public int search(int[] nums, int target){
        
    }
}

Class Solution{
	public int search(int[] nums, int target){
		//如果目标值小于数组的最小值，或者目标值大于数组的最大值 返回-1
		if(target < nums[0] || target > nums[nums.length-1]){
			return -1;
		};
        int left = 0;
        int right = nums.length - 1;
		//进行二分查找，最终的条件是left和right是否交叉
		//——>如果数组只有一个元素，那么会出现死循环的情况
		if(left <= right){
			mid = left + ((right - left)>>1);//——>1.如果是mid = (left + right)/2;测试集过大出现超过int的数据范围的情况。
		}else if(target == nums[mid]){//如果刚好mid值等于目标值
			return 1;
		}else if(target > nums[mid]){
			left = mid + 1;//2.这里+1，为什么不是left = mid？——>如果是单个元素的时候就进入了死循环
		}else{//等价于target < nums[mid]
			right = mid - 1;
		}
	}
	return -1;//如果以上条件都不满足，那么说明target是属于头尾数组元素范围之内，但不属于数组中的任何一个元素，所以返回-1。
}

题解：

class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid; // 最后返回下标
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            }

        }
        return -1;
    }

}

一、mid = (left + right)/2 出现超过int范围问题

如果在确定mid的时候，测试集的nums数组元素过大，会出现超过int范围问题。

二、出现数组越界

 如果所有条件都不满足，那么说明target是属于头尾数组元素范围之内，但不属于数组中的任何一个元素，所以返回-1。

举例：比如数组为[10, 20, 30, 40]，目标值为25。这时候二分法在查找过程中，中间元素是20或30，然后继续查找，直到循环结束，未找到，返回-1。

四、结束条件：left和right交叉

其他写法可能出现的问题：

为什么是left = mid + 1;或者是right = mid -1;？为什么不用left = mid;或者right = mid？——>会出现死循环

因为如果nums数组，如果只有一个元素，那么left和right都指向同一个元素，那么让left = mid后，left的值还是没有改变，陷入死循环。