编程算法案例9

折半查找

1.问题描述

N个有序整数数列已放在一维数组中，利用二分查找法查找整数m在数组中的位置。若找到，则输出其下标值；反之，则输出“Not be found!”。

2.问题分析

题目中给定了一个有序整数数列，我们需要使用二分查找法来查找该数列中的某个整数m，即找到其在数组中的位置并输出下标。如果整数m不存在于数组中，则需输出“Not be found!”。对于这个问题，我们可以使用二分查找（也称折半查找）算法来实现，其基本思路是每次将查找区间缩小一半，直到找到目标值或者剩余的区间为空为止。因为每次查找后实际上都将区间缩小一半，所以这是一种十分高效的查找算法。

3.算法设计

为了实现二分查找算法，我们需要先定义两个指针，即查找区间的左、右端点left和right（初始时分别为数组第一个元素和最后一个元素），然后在每一轮迭代中求出中间位置mid，判断target与arr[mid]的大小关系，如果target小于arr[mid]，则在[left, mid-1]区间继续查找；如果target大于arr[mid]，则在[mid+1, right]区间继续查找；否则找到了target，返回mid即可。具体实现可以参考以下代码：

Python代码实现

def binarySearch(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    print("Not be found!")
    return None

在上述代码中，我们首先定义了两个指针left和right，初始时分别为数组第一个元素下标和最后一个元素下标。然后在while循环中，我们不断计算left和right的中间位置mid，并判断target与arr[mid]的大小关系。如果target小于arr[mid]，则说明target位于[left, mid-1]区间内，则将右端点right更新为mid-1；如果target大于arr[mid]，则说明target位于[mid+1, right]区间内，则将左端点left更新为mid+1。如此重复上述过程，直到查找区间为空，即left > right，此时说明target不在数组中，输出“Not be found!”即可。

     程序运行结果

为了验证我们实现的二分查找算法的正确性，我们可以编写以下程序并运行：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
result = binarySearch(arr, target)
if result is not None:
    print("The target is at index", result)

上述程序首先定义了一个有序数组arr和要查找的目标整数target，然后调用binarySearch函数进行二分查找，并将返回值保存在变量result中。最后，如果result不为None，则说明找到了target，输出其下标即可。

当我们运行上述程序时，输出结果为：

The target is at index 6

可以看到，程序正确地输出了target在数组中的下标，验证了我们实现的二分查找算法的正确性。

JAVA代码实现

public class BinarySearch {
    public static 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) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println("Not be found!");
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 7;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("The target is at index " + index);
        }
    }
}

上述代码中，我们定义了一个静态方法binarySearch，接受一个有序整型数组arr和目标整数target并返回目标整数在数组中的下标（如果找到）。在方法中，我们维护了左端点left和右端点right，并在while循环中不断计算中间点mid，并与target进行比较，如果mid小于target，则在右半区间[left, mid-1]中继续查找，否则在左半区间[mid+1, right]中继续查找，直到查找区间为空。如果最后仍然没有找到target，则输出“Not be found!”。在main函数中，我们定义了一个有序数组和要查找的目标整数，并调用binarySearch方法进行查找，最后输出查找结果。

执行上述Java程序，输出结果为：

The target is at index 6

 

C++代码实现

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << "Not be found!" << endl;
    return -1;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 7;
    int index = binarySearch(arr, target);
    if (index != -1) {
        cout << "The target is at index " << index << endl;
    }
    return 0;
}

述代码中，我们使用了vector作为有序数组的数据结构。定义了一个binarySearch函数，接受一个vector类型的有序数组arr和目标整数target并返回目标整数在数组中的下标（如果找到）。在函数中，我们维护了左端点left和右端点right，并在while循环中不断计算中间点mid，并与target进行比较，如果mid小于target，则在右半区间[left, mid-1]中继续查找，否则在左半区间[mid+1, right]中继续查找，直到查找区间为空。如果最后仍然没有找到target，则输出“Not be found!”。在main函数中，我们定义了一个有序数组和要查找的目标整数，并调用binarySearch方法进行查找，最后输出查找结果。

执行上述C++程序，输出结果为：

The target is at index 6

可以看出，程序正确地实现了二分查找算法，能够正确地返回目标整数在数组中的下标。