如何在一个有序数组中查找一个元素的位置？

在有序数组中查找一个元素的位置,可以使用二分查找算法。二分查找是一种高效的查找算法,逻辑如下:

• 1. 首先,找出数组的中间位置 mid。
• 2. 如果中间位置的元素正是要查找的元素,则返回 mid。
• 3. 如果中间位置的元素大于要查找的元素,则在数组的左半部分进行查找。
• 4. 如果中间位置的元素小于要查找的元素,则在数组的右半部分进行查找。
• 5. 重复步骤 1 到 4,直到找到要查找的元素,或数组空间搜索完毕。

举个例子,假设有序数组为 [1, 2, 3, 4, 5, 6, 7],要查找的元素为 5:
首先 mid = (1 + 7) / 2 = 4,数组中间位置的元素为 4。
4 小于要查找的元素 5,所以在右半部分 [5, 6, 7] 中继续查找。
mid = (5 + 7) / 2 = 6,数组中间位置的元素为 6。
6 大于要查找的元素 5,所以在左半部分 [5] 中继续查找。
找到要查找的元素 5,位置在数组中的下标为 5。
那么这个算法的时间复杂度是 O(logN),因为每次都把查找区间减半。空间复杂度是 O(1),只需要常数空间存储几个变量。
总之,二分查找是一种效率很高的在有序数组中查找元素的算法。利用分治的思想,每次都将查找区间减半,从而达到快速查找到目标元素的目的。

这里是一个二分查找算法的Java实现示例:

public int binarySearch(int[] nums, int target) {
    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 {
            right = mid - 1;
        }
    }

    return -1;  // 未找到目标元素
}

这个方法接收两个参数:

• nums:要查找的有序数组
• target:要查找的目标元素
  它使用左右指针 left 和 right 来缩小查找区间,每次取中间位置 mid,判断 mid 是目标元素还是 target 较大/小,从而决定在左半部分或右半部分继续查找。
  如果找到目标元素,则返回其在数组中的位置下标。如果数组搜索完毕仍未找到,则返回 -1。
  例如,对于数组 [1, 2, 3, 4, 5, 6, 7],查找目标元素 5 的过程是:
• left = 0, right = 7, mid = 3,nums[3] < 5,左指针 left 移到 4
• left = 4, right = 7, mid = 5,nums[5] == 5,返回 5
  所以这个方法的返回值为 5,表示元素 5 在数组中的位置下标为 5。
  这个就是二分查找算法的简单实现,时间复杂度为 O(logN),可以很高效地在有序数组中查找某个目标元素。