“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

Today and you share a simple algorithm, flower elder brother algorithm is not fine, look forward to learning more with partners, in the comment area to teach a few, tomorrow will start to move bricks, row up.

Subject analysis

Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

  • Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Interpretation: 9 appears in nums with subscript 4

  • Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Description: 2 does not exist in NUMs so -1 is returned

  • Tip:

You can assume that all elements in NUMS are not repeated. N will be between [1, 10000]. Each element of nums will be between [-9999, 9999]. Number of passes 322,230 Number of submissions 583,055

The core idea of binary search is to divide n elements into two parts and compare the size relationship between a[n/2] and target:

  1. If x=a[n/2], target is found.
  2. If x
  3. If x>a[n/2], you only need to continue searching for target in the right half of array A;

The code analysis

  • Code sample
public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length-1;
    while (left <= right){
        int mid =left + ((right - left) >> 1);
        if (target == nums[mid]){
            return mid;
        }else if(target < nums[mid]){
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    return -1;
}
Copy the code

  • Mid = (left+ high) /2.

  • Then compare target with a[mid] :

    1. If a[mid] == target, the search succeeds, and the search stops.
    2. If a[mid]> target, select right=mid; if a[mid]> target, select right=mid;
    3. If a[mid]
    4. Compare the value of the current variable left and right, if left≤right, repeat the previous step, if left>right, there is no target element in the array, return -1.

Pay attention to the point

Right =nums.length-1, which is the index position to the last element of the array. It is equivalent to the closed interval [left,right].

(right-left) >> 1: equivalent to (rigth-left)/2.

\