• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Daily brush algorithm

Topic describes

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].

The problem solving

These two points clearly tell us that binary search can be used

1. The most general traversal

for(int i=0; i<nums.length; i++) {if (target == nums[i]) {
                returni; }}return -1;
Copy the code

Binary search

Specify the left and right boundaries of the current array, then loop through while until left is greater than right

The target value is compared to the median value, equal to or select the group, and then loop through the group.

// Left and right represent the range, maximum and minimum of the selected array
        int left = 0;
        int right = nums.length -1;
        // Only less than is not enough, only one element must be equal
        while(left <= right) {
            // take the middle value
            int mid = (left + right);
            // The intermediate values are compared to determine which group to go to
            if (target == nums[mid]) {
                return mid;
            }else if (target < nums[mid]) {
                // Both the left and right boundary values need to be -1 and +1, otherwise the loop will be infinite
                right = mid - 1;
            }else {
                left = mid + 1; }}return -1;
Copy the code

You can optimize mid, so to prevent overflow, you can write it this way

int middle = left + ((right - left) / 2)
Copy the code

The Arrays method class integrates methods

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
Copy the code