力扣二分搜索的总结

二分搜索总结

找目标数

有序数组(无重复元素)

力扣704

基本写法

class Solution {
   
    public int binarySearch(int[] nums, int target) {
   
        int l = 0, r = nums.length-1;
        while(l <= r ){
   
            //int mid = l + (r -l)/2;
            int mid = l + (r -l >> 1);
            if(nums[mid] == target){
   
                return mid;
            }
            else if (nums[mid] < target){
   
                l = mid + 1;
            }
            else {
   
                r = mid - 1;
            }
        }
        return -1;
    }
}

力扣35

基本写法

class Solution {
   
    public int searchInsert(int[] nums, int target) {
   
        int l = 0;
        int r = nums.length-1;
        while(l <= r){
   
            int mid = l + (r-l >>2);
            if(nums[mid] == target){
   
                return mid;
            }
            else if(nums[mid] < target){
   
                l = mid+1;
            }
            else{
   
                r = mid-1;
            }
        }
        return l;
    }
}

有序数组(元素可重复)

力扣34

返回第一个(最左)等于target的索引值, 返回最后一个(最右)等于target的索引值

public int binarySearchLeft(int[] nums, int target){
   
        int l = 0, r = nums.length-1;
        while(l <= r){
   
            int mid = (l + r)>>>1;
            if(nums[mid] == target){
   
                if(mid == 0 || nums[mid-1] < target){
   
                    return mid;
                }
                r = mid - 1;
            }
            else if(nums[mid] > target){
   
                r = mid - 1;
            }
            else{
   
                l = mid + 1;
            }
        }
        return -1;
}
 public int binarySearchRight(int[] nums, int target){
   
        int l = 0, r = nums.length-1;
        while(l <= r){
   
            int mid = (l + r)>>>1;
            if(nums[mid] == target){
   
                if(mid == nums.length-1 || nums[mid+1] > target){
   
                    return mid;
                }
                l = mid + 1;
            }
            else if(nums[mid] > target){
   
                r = mid - 1;
            }
            else{
   
                l = mid + 1;
            }
        }
        return -1;
 }

旋转数组(无重复元素)

力扣33

没有重复元素的部分有序数组,搜索旋转排序数组
自己写的

//自己写的
class Solution {
   
    public int search(int[] nums, int target) {
   
        int l = 0, r = nums.length-1;
        while(l <= r){
   
            int mid = (l + r) >>> 1;
            if(nums[mid] == target){
   
                return mid;
            }
            else if(nums[mid] > target){
   
                //当l和r之间存在旋转点的时候,且target数值小于左指针的数值时,表示左指针到数组最大值都是无效的,其实这时候应该将l指向最小的那个数,但是无法做到,只能将l++,效率低了一些
                if(nums[r] < nums[l] && target < nums[l]){
   
                    l++;
                }
                else{
   
                    r = mid - 1;
                }
            }
            else{
   
                //当l和r之间存在旋转点的时候,且target数值大于右指针的数值时,表示数组最小值到右指针所指的数都是无效的,其实这时候应该将r指向最大的那个数,但是无法做到,只能将r--,效率低了一些
                if(nums[r] < nums[l] && target > nums[r]){
   
                    r--;
                }
                else{
   
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
}

别人的思路

//别人的思路
public int search(int[] nums, int target) {
   
    int l = 0, r = nums.length - 1;
    while (l <= r) {
   
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {
   
            return mid;
        }
        // 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段 
        if (nums[mid] >= nums[l]) {
   
            // 再判断 target 是在 mid 的左边还是右边,从而调整左右边界 l 和 r
            if (target >= nums[l] && target < nums[mid]) {
   
                r = mid - 1;
            } else {
   
                l = mid + 1;
            }
        } else {
   
            if (target > nums[mid] && target <= nums[r]) {
   
                l = mid + 1;
            } else {
   
                r = mid - 1;
            }
        }
    }
    return -1;
}

力扣153

寻找旋转排序数组中的最小值 部分有序数组找最小值,不含重复元素

class Solution {
   
    public int findMin(int[] nums) {
   
        int l = 0;
        int r = nums.length-1;
        while(l < r){
   
            int mid = (r-l)/2+l;
            if(nums[mid] < nums[r]){
   
                r = mid;
            }
            else{
   
                l = mid + 1;
            }
        }
        return nums[r];
    }
}

旋转数组(元素可重复)

力扣81

有重复元素的部分有序数组(旋转数组)
自己写的,只需要把nums[r] < nums[l] 改为 nums[r] <= nums[l]

//自己写的
class Solution {
   
    public boolean search(int[] nums, int target) {
   
        int l = 0, r = nums.length-1;
        while(l <= r){
   
            int mid = (l + r) >>> 1;
            if(nums[mid] == target){
   
                return true;
            }
            else if(nums[mid] > target){
   
                //当l和r之间存在旋转点的时候,且target数值小于左指针的数值时,表示左指针到数组最大值都是无效的,其实这时候应该将l指向最小的那个数,但是无法做到,只能将l++,效率低了一些
                if(nums[r] <= nums[l] && target < nums[l]){
   
                    l++;
                }
                else{
   
                    r = mid - 1;
                }
            }
            else{
   
                //当l和r之间存在旋转点的时候,且target数值大于右指针的数值时,表示数组最小值到右指针所指的数都是无效的,其实这时候应该将r指向最大的那个数,但是无法做到,只能将r--,效率低了一些
                if(nums[r] <= nums[l] && target > nums[r]){
   
                    r--;
                }
                else{
   
                    l = mid + 1;
                }
            }
        }
        return false;
    }
}

别人的思路,在上一个题的基础上,用一个if保证左指针指的数和mid指针指的数不相同,否则无法在后面判断mid在前半部分还是后半部分

//别人的思路
class Solution {
   
    public boolean search(int[] nums, int target) {
   
        int l = 0, r = nums.length - 1;
        while (l <= r) {
   
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
   
                return true;
            }
            if(nums[l] == nums[mid]){
   
                l++;
                continue;
            }
            // 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段 
            if (nums[mid] > nums[l]) {
   
                // 再判断 target 是在 mid 的左边还是右边,从而调整左右边界 l 和 r
                if (target >= nums[l] && target < nums[mid]) {
   
                    r = mid - 1;
                } else {
   
                    l = mid + 1;
                }
            } else {
   
                if (target > nums[mid] && target <= nums[r]) {
   
                    l = mid + 1;
                } else {
   
                    r = mid - 1;
                }
            }
        }
        return false;
    }
}

力扣154

寻找旋转排序数组中的最小值 II,含有重复元素,和之前的处理方法一样

class Solution {
   
    public int findMin(int[] nums) {
   
        int l = 0, r = nums.length-1;
        while(l < r){
   
            int mid = l + (r - l >>1);
            //r--不会错过最小值,因为mid在r前面,两个的值相等,保证后序能判断mid是属于左部分还是右部分
            if(nums[mid] == nums[r]){
   
                r--;
                continue;
            }
            if(nums[mid] < nums[r]){
   
                r = mid;
            }
            else{
   
                l = mid +1;
            }
        }
        return nums[r];
    }
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务