Array - 704. Binary search

1 Title Description

704. Two points search
     Given a n The elements are ordered （ Ascending ） integer array nums And a target value target , Write a function search nums Medium target, If the target value has a return subscript , Otherwise return to -1.

2 Title Example

Example 1:

Input : nums = [-1,0,3,5,9,12], target = 9
Output : 4
explain : 9 Appear in the nums And the subscript is 4

Example 2:

Input : nums = [-1,0,3,5,9,12], target = 2
Output : -1
explain : 2 non-existent nums So back to -1

3 Topic tips

1. You can assume nums All elements in are not repeated .
2. n Will be in [1, 10000] Between .
3. nums Each element of will be in [-9999, 9999] Between .

4 Ideas

The premise of this topic is that the array is an ordered array , At the same time, the title also emphasizes that there are no duplicate elements in the array , Because once there's a repeating element , The element subscript returned by binary search method may not be unique , These are the prerequisites for using dichotomy , When you see that the Title Description meets the above conditions , But think about whether you can use dichotomy .

People often write dichotomy in disorder , Mainly because the definition of interval is not clear , The definition of interval is invariant . In the process of binary search , Keep invariants , Is in the while Every boundary treatment in the search must adhere to the operation according to the definition of interval , This is the loop invariant rule .

Write dichotomy , Interval is generally defined in two ways , Close left and close right [left, right], Or close left and open right [left, right).

5 My answer

（ Version of a ） Left closed right closed interval

class Solution {
    
    public int search(int[] nums, int target) {
    
        int left = 0, right = nums.length;
        while (left < right) {
    
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}

（ Version 2 ） Left closed right open interval

class Solution {
    
    public int search(int[] nums, int target) {
    
        int left = 0, right = nums.length;
        while (left < right) {
    
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}