By

Contents
  1. 1. 题目
  2. 2. 难点
  3. 3. 解题思路

题目

给定一个 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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

难点

数组，二分法

解题思路

方法1
递归二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int search(int[] nums, int target) {
        int begin = 0;
        int end = nums.length - 1;
        if(nums[0] > target || nums[end] < target){
            return -1;
        }
        if(nums[0] == target ){
            return 0;
        }
        if(nums[end] == target){
            return end;
        }
        return binarySearch(0, end, nums, target);
    }
public int binarySearch(int start, int end, int[] nums, int target){

    if(nums[start] == target ){
        return nums[start];

    }
    if(nums[end] == target){
        return nums[end];

    }
    int half = (end - start) / 2 ;
    if(half == 0){
        return -1;
    }
    int halfnum = nums[half + start];
    if(halfnum == target){
        return half + start;
    }else if(halfnum < target){
        return binarySearch(half + start, end , nums, target);
    }else{
        return binarySearch(start , half + start, nums, target);
    }


    }
}

思路2
看了题解，理解了二分法，又重新实现，关键在于边界的选择，开闭，通过理论的分析，比自己写的要很很多。
二分法的适用条件，1.没有重复数据，2.有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

public int search(int[] nums, int target) {

    int left = 0;
    int right = nums.length - 1;
    if(nums[0] > target || nums[right]< target){
        return -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;

    }
}
Contents
  1. 1. 题目
  2. 2. 难点
  3. 3. 解题思路