二进制搜索 - 在给定数组中查找目标索引

Question

这是leetcode上关于二分查找的第一道题。我们被要求 return 给定数组中目标的索引。我第一次尝试解决方案如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int result = -1;
        for(int i = 0; i < nums.size(); i++){
            if (nums[i] == target)
                result = i;
          
        }
        return result;
    }
};

如果我没有两次放置 return 结果，我会收到一条消息，提示由于某种原因超时。无论如何，对于这段代码下面的数组和目标 returns 16 的无意义值，当它应该 return 4:

[-1,0,3,5,9,12]
9

我和一个朋友讨论过，他本着同样的精神在Python中提出了一个解决方案：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = -1
        for i in nums:
            l += 1
            if i == target:
                print(l)
                return l

这个效果很好。不过，我看不出它与 C++ 中的有何不同。这在某种程度上与 Python 和 C 处理索引的方式有关吗？为什么 C++ 解决方案不起作用？抱歉，如果这些都是非常愚蠢的问题，我对一般的编程还很陌生。欢迎任何帮助。

编辑：我将循环条件固定为 i < nums.size()，这是我之前没有注意到的。这解决了我遇到的超时问题，并允许我将 return 放在 for 循环之外，但是现在由于某种原因我得到了 6 的值。

编辑 2：将 if 语句修正为 result = i，解决了所有问题。感谢 Mark 注意到这个非常愚蠢的错误。现在一切都很好。谢谢大家。

Answer 1

在 Wiki
这是 C++ 中的二进制搜索：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

using ValueType = std::uint_fast16_t;

static const struct Solution {
    static const int search(
        const std::vector<int>& nums,
        const int target
    ) {
        ValueType lo = 0;
        ValueType hi = std::size(nums) - 1;

        while (lo < hi) {
            ValueType mid = lo + (hi - lo) / 2;

            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) {
                lo = mid + 1;

            } else {
                hi = mid;
            }
        }

        return lo == hi && nums[lo] == target ? lo : -1;
    }
};

在Python中：

class Solution:
    def search(self, nums, target):
        if not nums:
            return -1
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] >= nums[lo]:
                if nums[lo] <= target <= nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] <= target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

这里是LeetCode的官方解之一，也有评论：

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def find_rotate_index(left, right):
            if nums[left] < nums[right]:
                return 0
            
            while left <= right:
                pivot = (left + right) // 2
                if nums[pivot] > nums[pivot + 1]:
                    return pivot + 1
                else:
                    if nums[pivot] < nums[left]:
                        right = pivot - 1
                    else:
                        left = pivot + 1
                
        def search(left, right):
            """
            Binary search
            """
            while left <= right:
                pivot = (left + right) // 2
                if nums[pivot] == target:
                    return pivot
                else:
                    if target < nums[pivot]:
                        right = pivot - 1
                    else:
                        left = pivot + 1
            return -1
        
        n = len(nums)
        
        if n == 0:
            return -1
        if n == 1:
            return 0 if nums[0] == target else -1 
        
        rotate_index = find_rotate_index(0, n - 1)
        
        # if target is the smallest element
        if nums[rotate_index] == target:
            return rotate_index
        # if array is not rotated, search in the entire array
        if rotate_index == 0:
            return search(0, n - 1)
        if target < nums[0]:
            # search on the right side
            return search(rotate_index, n - 1)
        # search on the left side
        return search(0, rotate_index)

Python 没有 int 溢出 (mid = start + (end - start) // 2)。这是 LeetCode 官方给出的另一个解决方案：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[start]:
                if target >= nums[start] and target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                if target <= nums[end] and target > nums[mid]: 
                    start = mid + 1
                else:
                    end = mid - 1
        return -1

二进制搜索 - 在给定数组中查找目标索引

Binary Search - Find Index of Target in a Given Array

c++

python

binary-search