Description

力扣

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
 

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

Solution

  1. 用二分的前提是升序且不重复。
  2. 需要注意边界条件的细节。
  3. 全闭能等，右闭减开不减。

左右闭合

  1. [left, right] -> 都能取到，所以left 从 第一个下标（0）开始，right 从最后一个下标开始（nums.length - 1）。
  2. left 和 right 可能会相等，所以while 条件里是 <=。
  3. 因为左右皆闭合，如果nums[middle] <> target, 左右需要加减1。
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int middle = left + (right - left) / 2;
            if (nums[middle] > target){
                right = middle -1 ;
            } 
            else if (nums[middle] < target){
                left = middle + 1;
            }
            else {
                return middle;
            }
        }
        return -1;
    }
};

左闭右开

  1. [left, right) -> right 需要超出边界1位，所以left 从 第一个下标（0）开始，right 从最后一个下标+1开始（nums.length ）。
  2. left 和 right 不可能相等，所以while 条件里是 <。
  3. 因为左闭右开，如果nums[middle] <> target, 左需要加1，右不需要减1。
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right){
            int middle = left + (right - left) / 2;
            if (nums[middle] > target){
                right = middle ;
            } 
            else if (nums[middle] < target){
                left = middle + 1;
            }
            else {
                return middle;
            }
        }
        return -1;
    }
};

Notice Points

关于计算长度的几个方法

  • length : Arrays (int[], double[], String[]) — 取得Array的长度
  • length() : String related Object(String, StringBuilder, etc) — 取得字符串的长度
  • size() : Collection Object (ArrayList, Set, etc) — 取得泛型集合大小
import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        String[] arr = {"a", "b", "c"};
        String s = "123456";
        Set<String> set = new HashSet();
        set.add("example");

        System.out.println(arr.length); //3
        System.out.println(s.length()); //6
        System.out.println(set.size()); //1
     }
}