c+＋，利用折半查法从一个升序排列的数列中查找某数是否存在

在 C++ 中，折半查找（也称为二分查找），是一种高效的搜索算法，适用于已排序的数组或列表。其基本思想是每次将待查找区间的中间元素与目标值进行比较。如果目标值等于中间元素，则查找成功；若目标值小于中间元素，则在左半区间继续查找；若大于中间元素，则在右半区间查找。这个过程不断缩小查找范围，直到找到目标值或确定它不存在于序列中。

以下是使用 C++ 实现折半查找的基本步骤：

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 注意这里对除法进行了整数化处理

        if (nums[mid] == target) {
            return mid; // 找到目标，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标大于当前中间值，移动到右侧
        } else {
            right = mid - 1; // 目标小于当前中间值，移动到左侧
        }
    }

    return -1; // 如果未找到，返回 -1 表示目标不存在
}

相关问题

查找与排序算法编程与训练

以下是一些常见的查找和排序算法，以及相应的编程语言示例和练习题：

## 查找算法

### 顺序查找

顺序查找也叫线性查找，是一种简单直接的查找方法。它从表的一端开始，顺序扫描线性表，逐个将被查找关键字和各数据元素的关键字进行比较，当查找到关键字相同时，查找成功，否则查找失败。

示例代码（Python）：

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

练习题：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，并且同样的元素不能被重复利用。示例：给定 nums = [2, 7, 11, 15], target = 9，因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]。

### 二分查找

二分查找也叫折半查找，是一种时间复杂度为O(log n)的查找算法。它要求待查找的序列有序，通过不断缩小查找范围，最终找到目标元素。

示例代码（Java）：

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

练习题：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

## 排序算法

### 冒泡排序

冒泡排序是一种简单直观的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置，直到没有任何一对数字需要交换为止。

示例代码（C++）：

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

练习题：给定一个无序的整数数组，找到其中最长上升子序列的长度。

### 快速排序

快速排序是一种高效的排序算法，它利用了分治思想，在待排序的数列中选择一个元素作为基准值，将数列分成两部分，小于基准值的放在左边，大于基准值的放在右边，然后递归地对左右两部分进行排序。

示例代码（Python）：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

练习题：给定一个由 n 个整数组成的数组 nums 和一个目标值 target，将所有小于 target 的元素移到数组的左侧，将所有大于 target 的元素移到数组的右侧，然后返回数组。