[daily question] dichotomy - find a single dog (Bushi)

️ Winter vacation xinkeng —— Code Fox's daily notes
The winter vacation is about to expire

540. A single element in an ordered array -Mid( Binary search deformation )

Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int l=0;
        int r=nums.length-1;
        while(l<r){
    
            int mid=l+(r-l)/2;
            // If mid The front is orderly , There must be an even subscript equal to the value of its next odd subscript , Take this as a condition for narrowing the scope 
            if((mid%2==0&&nums[mid]==nums[mid+1])||(mid%2==1&&nums[mid]==nums[mid-1])){
    
                l=mid+1;
            }
            else if((mid==0||nums[mid]!=nums[mid-1])&&(mid==nums.length-1||nums[mid]!=nums[mid+1])){
    
                return nums[mid];
            }
            else{
    
                r=mid-1;
            }
        }
        return nums[l];
    }
}

35. Search insert location

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

Please use a time complexity of O(log n) The algorithm of .

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(target<nums[mid]){
    
                r=mid-1;
            }
            else if(target==nums[mid]){
    
                return mid;
            }
            else{
    
                l=mid+1;
            }
        }
        if(nums[l]>=target)
            return l;
        else
            return l+1;
    }
}

ending

Title source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems

️ Focus on the author , Take you to brush the questions , Learn the most commonly used algorithm skills from simple algorithm problems （ Winter vacation every day ）
️ Pay attention to the author's questions —— Simple to advanced , Let you unknowingly become a ruthless problem brushing machine , If you have any questions, please send a private letter