二分查找

二分查找

在升序数组中查询一个等于target的值存在则返回索引，不存在返回-1；

首先看题意，这就不就是标准的二分查找吗，开始写。while(left<right)呢还是while(left<=right)。懵逼了。算了 看答案吧，下次还是记不住。使用小于的情况在于right=nums.length;这种情况需要处理返回值。而使用小于等于，则想当于处理闭区间{0,nums.length-1},不需要处理返回值。

//小于等于
public int midFind(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){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }
        }
        return -1;
    }
// 小于
 public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        while(left < right ){
            int mid=(right+left)/2;
            if(nums[mid]==target){
                return mid;
            }else if (nums[mid]>target){
                right=mid-1;
            }else if (nums[mid]<target){
                left=mid+1;
            }
        }
        if(left >= nums.length){
            return -1;
        }
        return nums[left]==target?left:-1;
    }

在有序数组中查询左边第一个等于target的值存在则返回索引，不存在返回-1；可能存在重复

在标准二分查找中我们知道了什么时候使用小于还是小于等于，那么对于有重复数据的有序数组，我们要获取左边第一个我们要怎么处理呢。关键就得定位到 nums[mid]==target的处理了，对于取左边第一个还是右边第一个，就在于控制左右指针在 nums[mid]==target进行赋值运算。

//小于等于
public int midFind(int[] nums,int target){
        int left = 0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                right=mid-1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }
        }
        if(left>=nums.length||nums[left]!=target){
        return -1;
        }
        return left;
    }
// 小于
 public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        while(left < right ){
            int mid=(right+left)/2;
            if(nums[mid]==target){
                right=mid-1;
            }else if (nums[mid]>target){
                right=mid-1;
            }else if (nums[mid]<target){
                left=mid+1;
            }
        }
        if(left >= nums.length){
            return -1;
        }
        return nums[left]==target?left:-1;
    }

在有序数组中查询右边第一个等于target的值存在则返回索引，不存在返回-1；可能存在重复

//小于等于
public int midFind(int[] nums,int target){
        int left = 0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }
        }
        if (right < 0 || nums[right] != target){
	    return -1;
	}  
        return right;
    }
// 小于
 public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        while(left < right ){
            int mid=(right+left)/2;
            if(nums[mid]==target){
                left=mid+1;
            }else if (nums[mid]>target){
                right=mid;
            }else if (nums[mid]<target){
                left=mid+1;
            }
        }
        if (right<=0){
            return -1;
        }
       return nums[left-1]==target?left-1:-1;
    }