解题思路

  1. 基本二分查找思路：

    • 维护左右边界 和
    • 计算中间位置
    • 比较中间元素与目标值
    • 根据比较结果调整边界

  2. 查找第一次出现的位置：

    • 当找到目标值时，不要立即返回
    • 继续向左查找，看是否还有相同的值
    • 记录最左侧的位置

代码

class BinarySearch {
public:
    int getPos(vector<int>& A, int n, int val) {
        int left = 0;
        int right = n - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (A[mid] == val) {
                // 记录当前位置，继续向左查找
                result = mid;
                right = mid - 1;
            } else if (A[mid] > val) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        int left = 0;
        int right = n - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (A[mid] == val) {
                // 记录当前位置，继续向左查找
                result = mid;
                right = mid - 1;
            } else if (A[mid] > val) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

class BinarySearch:
    def getPos(self, A, n, val):
        left = 0
        right = n - 1
        result = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if A[mid] == val:
                # 记录当前位置，继续向左查找
                result = mid
                right = mid - 1
            elif A[mid] > val:
                right = mid - 1
            else:
                left = mid + 1
                
        return result

算法及复杂度

  • 算法：二分查找
  • 时间复杂度：，其中 为数组长度
  • 空间复杂度：，只使用常数额外空间