This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

I. Title Description:

Ii. Analysis of Ideas:

Known: ascending order, which can then be inferred not to repeat.

That’s easy to do, a simple dichotomy.

So, how do we write dichotomy?

while (left < right )
or
while (left <= right)

if(arr[mid] < target)
or
if(arr[mid] <= target)
Copy the code

It’s easy to obsess over the details, but I won’t give you the exact answer in this post. It’s a case-by-case approach

Iii. AC Code:

public int search(int[] nums, int target) {
    int len = nums.length;
    // Consider an empty array
    if (len == 0) {
        return -1;
    }
    int left = 0;
    int right = len - 1;
    
     while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            // The value of mid and the value to the left of mid are equal to target
            // Next search range is [mid + 1, right]
            left = mid + 1;
        } else {
            // Target < nums[mid]
            // We can see that mid and the right side of mid are less than target
            // The next search scope is [left, mid-1]
            right = mid - 1; }}return -1;
}
Copy the code

Iv. Summary:

The first is the condition for if, if sometimes there are duplicates, let you look for the first target/ the last target. How do you set the if condition? Arr [mid] == target

I personally do not recommend merging the three if judgments into two at this point, preserving the frame itself allows you to apply more experience to the question.

This is a very basic framework. In addition to short calls, you need to pay attention to three things:

  1. While condition, which determines when you stop looking, right
  2. I know that sometimes you can merge into two parts, but this will make you lose control of the framework. This is not recommended for beginners.
  3. Mid = left + (right-left)/2 (if len = 2)