|
也称折半查找算法、对数查找算法,是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找算法,分别用C语言,C++,java,python编写出来
下面是二分查找算法的不同语言实现示例:
1. C语言:
- #include <stdio.h>
- int binarySearch(int arr[], int left, int right, int target) {
- while (left <= right) {
- int mid = left + (right - left) / 2;
- if (arr[mid] == target)
- return mid;
- if (arr[mid] < target)
- left = mid + 1;
- else
- right = mid - 1;
- }
- return -1;
- }
复制代码 int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1)
printf("Element not found\n");
else
printf("Element found at index %d\n", result);
return 0;
}
2. C++:
- #include <iostream>
- int binarySearch(int arr[], int left, int right, int target) {
- while (left <= right) {
- int mid = left + (right - left) / 2;
- if (arr[mid] == target)
- return mid;
- if (arr[mid] < target)
- left = mid + 1;
- else
- right = mid - 1;
- }
- return -1;
- }
复制代码 int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1)
std::cout << "Element not found" << std::endl;
else
std::cout << "Element found at index " << result << std::endl;
return 0;
}
3. Java:
- public class BinarySearch {
- public static int binarySearch(int[] arr, int left, int right, int target) {
- while (left <= right) {
- int mid = left + (right - left) / 2;
- if (arr[mid] == target)
- return mid;
- if (arr[mid] < target)
- left = mid + 1;
- else
- right = mid - 1;
- }
- return -1;
- }
-
- }
复制代码 public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = binarySearch(arr, 0, arr.length - 1, target);
if (result == -1)
System.out.println("Element not found");
else
System.out.println("Element found at index " + result);
}
4. Python:
- def binarySearch(arr, left, right, target):
- while left <= right:
- mid = left + (right - left) // 2
- if arr[mid] == target:
- return mid
- if arr[mid] < target:
- left = mid + 1
- else:
- right = mid - 1
- return -1
复制代码
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binarySearch(arr, 0, len(arr) - 1, target)
if result == -1:
print("Element not found")
else:
print("Element found at index", result)
这些示例展示了使用不同编程语言实现二分查找算法的方式。请根据您选择的编程语言,使用相应的示例来实现二分查找算法。
扫码关注微信公众号,免费查看完整算法内容。
|
|