请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1
数据范围: , 数组中任意值满足
进阶:时间复杂度 ,空间复杂度
[-1,0,3,4,6,10,13,14],13
6
13 出现在nums中并且下标为 6
[],3
-1
nums为空,返回-1
[-1,0,3,4,6,10,13,14],2
-1
2 不存在nums中因此返回 -1
数组元素长度在[0,10000]之间数组每个元素都在 [-9999, 9999]之间。
int search(int* nums, int numsLen, int target ) { if(numsLen==0) return -1; int left=0,right=numsLen-1,mid; while(left<=right){ //当left>right时停止 mid=(left+right)/2; if(nums[mid]>target) right=mid-1; else if(nums[mid]<target) left=mid+1; else return mid; } return -1; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { // write code here if (nums.length == 0) return -1; int left = 0, right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (target == nums[mid]) return mid; if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return -1; } }
public int search (int[] nums, int target){ return search(nums,target,0,nums.length-1); } public int search (int[] nums, int target,int left,int right) { // write code here if(left>right ){ return -1; } int middle = (left+right)/2; if(nums[middle]==target){ return middle; }else if(nums[middle] < target){ return search(nums,target,middle+1,right); }else{ return search(nums,target,left,middle-1); } }
class Solution: def search(self , nums: List[int], target: int) -> int: # write code here left=0 right=len(nums)-1 while left<=right: mid=(right+left)//2 if nums[mid]==target: return mid elif nums[mid]>target: right=mid-1 elif nums[mid]<target: left=mid+1 return -1
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ function search( nums , target ) { // write code here let i = 0; while (i < nums.length) { if (nums[i] == target) { return i; } i++; } return -1; } module.exports = { search : search };
class Solution: def search(self , nums: List[int], target: int) -> int: # write code here length = len(nums) left = 0 right = length if length < 1: return -1 while left <= right: mid = int((left + right) / 2) if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { // write code here int start = 0, end = nums.size() - 1, middle; while (start <= end) { middle = start + ((end - start) >> 1); if (nums[middle] == target) return middle; else if (nums[middle] < target) start = middle + 1; else end = middle - 1; } return -1; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { // write code here int begin = 0; int end = nums.length-1; int mid = 0; while(begin<=end){ mid = (begin+end)/2; if(target == nums[mid]){ return mid; }else if (target<nums[mid]){ end = mid -1; }else if (target>nums[mid]){ begin = mid + 1; } } return -1; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { if(nums.length==0){ return -1; } 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 if(nums[mid]>target){ right = mid-1; } } return -1; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { // write code here if (nums.length == 0) { return -1; } int len = nums.length; int left = 0; int right = len - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = (mid > left) ? mid : left + 1; } else { right = (mid < right) ? mid : right - 1; } } return -1; } }
int search(int* nums, int numsLen, int target ) { // write code here if(!nums||!numsLen) { return -1; } int beg=0; int end=numsLen-1; int mid; while (beg<=end) { mid=(beg+end)/2; if(target==nums[mid]) { return mid; } else if(target>nums[mid]) { beg=mid+1; } else { end=mid-1; } } return -1; /* //时间复杂度不过关 int beg=0; int end=numsLen-1; while(target!=nums[(beg+end)/2]) { if(beg==end) { return -1; } if(target<nums[(beg+end)/2]) { end=(beg+end)/2-1; } else { beg=(beg+end)/2+1; } } return (beg+end)/2; */ }