【每日一题0715】二分查找

兴趣爱好交流 每日一题
1

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

提示：

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

题目难度：中等
题目来源：shoppe面试真题，力扣（LeetCode）

def search(nums: List[int], target: int) -> int:
    pass

assert search([-1,0,3,5,9,12], 9) == 4
assert search([-1,0,3,5,9,12], 2) == -1
2

def search(nums,target):
low,high = 0,len(nums)-1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
elif nums[mid] > target:
high = mid -1
return -1

3 
def search(nums: List[int], target: int) -> int:
    start = 0
    end = len(nums) -1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] > target:
            end = mid - 1
        elif nums[mid] < target:
            start = mid + 1
        else:
            return mid
    return -1
2 个赞
4 
class Solution:
    @classmethod
    def search(cls, nums: List[int], target: int) -> int:
        """
           1、初始化指针left=0.right=len(nums)-1
           2、比较中间元素mid和target，如果target=mid,返回mid，如果target < mid,则right -1,否则left +1
           :param nums:
           :param target:
           :return:int:
           """
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = (right + left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1


assert Solution.search(nums=[-1, 0, 3, 5, 9, 12], target=-1) == 0
assert Solution.search(nums=[-1, 0, 3, 5, 9, 12], target=12) == 5
assert Solution.search(nums=[-1, 0, 3, 5, 9, 12], target=8) == -1
5

‘’’
def search(nums: List[int], target: int) → int:
left = 0
right = len(nums) - 1
while(left < right):
mid = left + (right - left)/2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left

assert search([-1,0,3,5,9,12], 9) == 4
assert search([-1,0,3,5,9,12], 2) == -1
‘’’

6

请问哪里可以找到更多shopee的面试真题？？？？

def search(nums:list[int],target:int)->int:
    left=0
    right=len(nums)-1
    while left<=right:
        res=int((left+right)/2)
        if nums[res]==target:
            return res
        elif nums[res]<target:
            left=res+1
        elif nums[res]>target:
            right=res-1
    return -1

assert search([-1,0,3,5,9,12], 9)==4
assert search([-1,0,3,5,9,12], 2)==-1
7 
def search(nums, target):
    left,right = 0,len(nums)-1
    while left<=right:
        avg = left + (right-left) // 2
        if nums[avg] == target:
            return avg
        elif nums[avg] > target:
            right = avg-1
        else:
            left = avg+1
    return -1


assert search([-1,0,3,5,9,12], 9) == 4
assert search([-1,0,3,5,9,12], 2) == -1
8 
public int middleSearch(int[] li, int target) {
        int low = 0;
        int high = li.length - 1;

        while (low <= high) {
            int middle = (high + low) / 2;
            if (li[middle] == target) {
                return middle;
            } else if (li[middle] > target) {
                high = middle;
            } else if (li[middle] < target) {
                low = middle + 1;
            }
        }
        return -1;
    }
9

牛客网貌似有一些，我目前手上的都是我面的，或者朋友面过分享的。 :grin: