[array] binary search

1、 The basic idea

Prerequisite ： Ordered array + No repeating elements （ not essential ）
Put the array （ Default ascending order ） Separate from the middle , Compare with the intermediate value every time , If it is less than the middle value, you only need to find the left , If it is greater than the middle value, just look for the right , Equal to the intermediate value and directly return the subscript ！

2、 Exercises （ It is suggested to go first leetcode do , Then look at the answer ）

• 704 Two points search

​

//  Mode one ： Left and right closed [left,right]
class Solution {
    
    public int search(int[] nums, int target) {
    
        //  Closed interval ：r=nums.length-1
        int l = 0;int r = nums.length  - 1;
        //  Be careful ：l<=r
        //  Why is there an equal sign ？
        // [1], When there's only one element ,l=0,r=0,m=0,l==r It makes sense 
        while (l <= r){
    
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;
            else if (nums[m] > target) {
    
                //  Closed interval , So it is r=m-1
                r = m - 1;
            }else{
    
                l = m + 1;
            }
        }
        return -1;
    }
}

//  Mode one ： Left closed right away [left,right)
class Solution {
    
    public int search(int[] nums, int target) {
    
        //  Open range ：r=nums.length
        int l = 0;int r = nums.length;
        // [1], When there's only one element ,l=0,r=1,m=0, Elements can be compared , therefore l==r You can quit , It doesn't make sense 
        while (l < r){
    
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;
            else if (nums[m] > target) {
    
                //  Open range , So it is r=m
                r = m;
            }
            else {
    
                l = m + 1;
            }
        }
        return -1;
    }
}

• 35. Search insert location

//  Method 1 : Brute force 
//  Traversal array , Find insertion location 
//  If there is this element, the position is the insertion position ; Without this element , Then the first array position larger than the target element is the insertion position 
class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        for (int i = 0; i < nums.length; i ++) {
    
            if (nums[i] >= target)  return i;
        }
        return nums.length;
    }
}
//  Method 2 ： Two points search 
//  If this element exists in the array , Use bisection to find the position of this element and return 
//  Without this element , be r The position of is exactly smaller than the position of the target element , be r+1 It's where you need to insert 
class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        int l = 0; int r = nums.length - 1;
        while (l <= r){
    
            int m = l + (r - l) / 2;
            //  Equal to an element 
            if (nums[m] == target) return m;
            else if (nums[m] > target) {
    
                r = m - 1;
            }else{
    
                l = m + 1;
            }
        }
        //  Leftmost 
        //  Far right 
        //  After an element 
        return r + 1;
    }
}

• 34. Find the first and last positions of the elements in the sort array

//  Method 1 ： Two points search 
//  First, find the position of the element by bisection （ Because the position of repeated elements is not necessarily the leftmost or rightmost ）, Then slide the pointer on the left to find the leftmost , Slide right until you find the rightmost 
class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    
        int index = binarySearch(nums, target);
        if (index == -1) {
    
            return new int[]{
    -1, -1};
        }

        //  Left slide pointer 
        int left = index;
        while (left - 1 >= 0 && nums[left - 1] == target){
    
            left = left - 1;
        }
        //  Slide the pointer right 
        int right = index;
        while (right + 1 < nums.length && nums[right + 1] == target){
    
            right = right + 1;
        }
        return new int[]{
    left, right};
    }
    public int binarySearch(int[] nums, int target){
    
        int l = 0; int r = nums.length - 1;
        while (l <= r){
    
            int m = l + (r  - l) / 2;
            if (nums[m] == target) return m;
            else if (nums[m] > target) r = m - 1;
            else l = m + 1;
        }
        return -1;
    }
}
//  Method 2 ： Two points search 
//  If the element exists , Find the left and right boundaries through binary search 
//  If the element does not exist, return directly {-1,-1}
class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
		//  Only if any boundary is not found, there is no such element 
        if (rightBorder == -2 || leftBorder == -2){
    
            return new int[]{
    -1, -1};
        }
		//  The left and right boundaries are open intervals , As long as it exists, the interval must be greater than 1
        if (rightBorder - leftBorder > 1){
    
            return new int[]{
    leftBorder + 1, rightBorder - 1};
        }
        return new int[]{
    -1, -1};

    }
    //  Find the left boundary , This left boundary is required +1 Of 
    //  The left boundary is to find the first position smaller than the target value step by step from the right 
    public int getLeftBorder(int[] nums, int target){
    
        int l = 0; int r = nums.length - 1;
        int leftBorder = -2;
        while (l <= r){
    
            int m = l + (r - l) / 2;
            //  If the intermediate value is greater than or equal to the target value , be r = m - 1; At the same time, update the value of the left boundary 
            if (nums[m] >= target){
    
                r = m - 1;
                leftBorder = r;
            }else{
    
                l = m + 1;
            }
        }
        return leftBorder;
    }
    //  Find the right boundary , This right boundary is required -1 Of 
    //  Right border , Is to find the first position larger than the target value from the right 
    public int getRightBorder(int[] nums, int target){
    
        int l = 0; int r = nums.length - 1;
        int rightBorder = -2;
        while (l <= r){
    
            int m = l + (r - l) / 2;
            if (nums[m] > target){
    
                r = m - 1;
            }else{
    
                //  If the intermediate value is less than or equal to the target value , be l = m + 1; At the same time, update the value of the right boundary 
                l = m + 1;
                rightBorder = l;
            }
        }
        return rightBorder;
    }
}

• 69.x The square root of

//  Method 1 ： Brute force 
//  Traverse x, Know that the square of the first number is greater than the target value 
class Solution {
    
    public int mySqrt(int x) {
    
        // x = 0 A special case 
        int res = 0;
        // x = 1 A special case 
        if (x == 1) res = 1;
        for (long i = 1; i <= x / 2; i++){
    
            long tmp = i * i;
            if (tmp > x){
    
                res = (int)i - 1;
                break;
            }else{
    
                res = (int)i;
            }
        }
        return res;
    }
}
//  Method 2 ： Two points search 
//  from 0 To x, Find... By bisection , If the flat hair of a certain number is exactly equal to x Then return directly 
//  If there is no direct equal , be r Is the nearest integer value 
class Solution {
    
    public int mySqrt(int x) {
    
        int l = 0; int r = x;
        while (l <= r){
    
            long m = l + (r - l) / 2;
            long tmp = m * m;
            if (tmp == x){
    
                return (int)m;
            }else if (tmp > x){
    
                r = (int) m - 1;
            }else{
    
                l = (int) m + 1;
            }
        }
        return r;
    }
}

• 367. Effective complete square number

//  Two points search 
//  from 0 To num, If the flat hair of a certain number is exactly equal to num, Then return to true, Otherwise return to false
class Solution {
    
    public boolean isPerfectSquare(int num) {
    
        int l = 0; int r = num;
        while (l <= r){
    
            long m = l + (r - l) / 2;
            long tmp = m * m;
            if (tmp == num){
    
                return true;
            }else if (tmp > num){
    
                r = (int) m - 1;
            }else{
    
                l = (int) m + 1;
            }
        }
        return false;
    }
}

Thanks for reading , I am a Alson_Code, One likes to complicate simple problems , A program that simplifies complex problems ！