目录

目录

一、问题描述

描述

示例1

示例2

示例3

二、用python实现

三、用java实现

一、问题描述

描述

请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围：0 le len(nums) le 2times10^50≤len(nums)≤2×105 ， 数组中任意值满足 |val| le 10^9∣val∣≤109

进阶：时间复杂度 O(log n)O(logn) ，空间复杂度 O(1)O(1)

示例1

输入：[-1,0,3,4,6,10,13,14],13

返回值：6

说明：nums为空，返回-1

示例2

输入：[],3

返回值：-1

说明：nums为空，返回-1

示例3

输入：[-1,0,3,4,6,10,13,14],2

返回值：-1

说明：2 不存在nums中因此返回 -1

二、用python实现

 class Solution:
    def search(self , nums: List[int], target: int) -> int:
     
        left = 0  # 数组最左边的数字的索引为0
        right = len(nums) - 1  # 数据最右边的数字的索引为len(nums) -1
        while left <= right:   #表示候选区有值
            mid = (left+right)// 2
            if nums[mid] == target:  #待查找的值就是mid时返回mid 也就是这个值的索引
                return mid          
            elif nums[mid] < target: #待查找的值如果在mid的右边，那么将新的查找区间的left移动到mid+1位置
                left = mid + 1
            else:           
                right = mid -1    #待查找的值如果在mid的左边，那么新的查找区间的right就移动到mid-1
        else :
            return -1  # 如果没找到待查找的值就返回-1

三、用java实现

实现思路每步和上面python的一样 我就不写了

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