704. Binary search

Title:

Topic analysis:

Give an array and target value, find the location of the target value, and return the array subscript of the location. If there is no target value in the array, return - 1

The moment I see the problem, I think I can directly a for loop. I can finish writing and finish work directly. I can see the problem. Something's wrong. This problem is called binary search, so I need to use binary search to solve it.

Recall binary search:

By comparing the size relationship between the value of the middle position and the target value, we can constantly narrow the search range and know that the conditions set by ourselves are not met in the end

Code part:

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int 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) {
                left = mid + 1;
            } else{
                return mid;
            }
        }
        return -1;
    }
}

Code analysis:

Define two variables of type int to represent the leftmost and rightmost of the array. Because it is a binary search, left > right means that the target value is not found in the array, so there is no need to continue to cycle to find the target value.

Set mid in the loop to represent the intermediate value. Because left and right will be changed every time the loop, mid is initialized inside the loop.

Judgment: num [mid] is the value we are looking for. If the value we find is less than the target value, and because the array is in ascending order, all elements on the left side of mid will be less than the target value. There is no need to continue judgment. This is left = mid + 1; Similarly, the value found is greater than the target value, and all the values on the right side of mid are greater than the target value. There is no need to find.

Search insertion location

Title:
[external chain picture transfer failed. The source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-ar4ves2n-1641620870251)( https://cdn.jsdelivr.net/gh/fishyin/picodemo//img/202201072229212.png )]

Topic analysis:

Find the target value in the array. If not, return the position where the target value should be inserted.

Case 1: find the target value and return the subscript.

Case 2: the target value is not found. Finally, the left after the end of the cycle is returned

code:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int 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) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}

Finds the first and last positions of elements in a sorted array

Topic analysis:

Find the start position and end position of the target value. If not found, return [- 1, - 1]

Situation analysis:
Case 1: if the target value to be found is on the left or right of the array range, such as array {3,5,7}, and the target value is 2 or 9, it will directly return [- 1, - 1]

Case 2: the value to be found is within the array range, but there is no target value in the array. For example, if the array {3,5,7} has a target value of 4, it will directly return [- 1, - 1]

Case 3: the target value can be found in the array

We can define two methods to find the boundary, getLeftBorder() method to find the left boundary, and getrighterboard () method to find the right boundary

The code is as follows:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder (nums, target);
        int righterBorder = getRighterBorder (nums, target);
        if(leftBorder == -2 || righterBorder == -2) {
            return new int[] {-1, -1};
        }

        if(righterBorder - leftBorder > 1){
            return new int [] {leftBorder + 1, righterBorder - 1};
        }
        return new int[]{-1, -1};
    }
    
    public int getLeftBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int leftBorder = -2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
                leftBorder = right; 
            } else {
                left = mid + 1;
            }
        }
        return leftBorder;
    }
    
    public int getRighterBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int righterBorder = -2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {

                left = mid + 1;
                righterBorder = left;                
            }
        }
        return righterBorder;
    }
}