binary search - half-interval search - 二分法检索 - 折半检索 - 二分查找 - 折半查找

╰+攻爆jí腚メ 2023-02-11 04:50 10阅读 0赞

#  binary search - half-interval search - 二分法检索 - 折半检索 - 二分查找 - 折半查找 #

binary search, half-interval search, logarithmic search, or binary chop：二分法检索，折半检索，二分查找，折半查找

## 1. 查找过程 ##

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较。如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表。如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

## 2. 算法要求 ##

1.  必须采用顺序存储结构。
2.  必须按关键字大小有序排列。

## 3. recursive Binary Search ##

Recursive implementation of Binary Search

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    // C++ program to implement recursive Binary Search 
    // A recursive binary search function. 
    // It returns location of x in given array arr[l..r] is present, otherwise -1.
    int binary_search(int arr[], int left, int right, int target)
    {
    	if (left <= right)
    	{
    		int mid = left + (right - left) / 2;
    
    		// If the element is present at the middle itself. 
    		if (arr[mid] == target) {
    			return mid;
    		}
    
    		// If element is smaller than mid, then it can only be present in left subarray 
    		if (target < arr[mid]) {
    			return binary_search(arr, left, mid - 1, target);
    		}
    
    		// Else the element can only be present in right subarray 
    		if (target > arr[mid]) {
    			return binary_search(arr, mid + 1, right, target);
    		}
    	}
    
    	// We reach here when element is not present in array.
    	return -1;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int arr[] = { 2, 3, 4, 10, 40 };
    	int target = 5;
    	int num = sizeof(arr) / sizeof(arr[0]);
    	cout << "sizeof(arr) = " << sizeof(arr) << endl;
    	cout << "sizeof(arr[0]) = " << sizeof(arr[0]) << endl;
    	cout << "target = " << target << endl;
    	int result = binary_search(arr, 0, num - 1, target);
    	(-1 == result) ? cout << "Element is not present in array." << endl : cout << "Element is present at index " << result << "." << endl;
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    // C++ program to implement recursive Binary Search 
    // A recursive binary search function. 
    // It returns location of x in given array arr[l..r] is present, otherwise -1.
    int binary_search(int arr[], int left, int right, int target)
    {
    	if (left <= right)
    	{
    		int mid = left + (right - left) / 2;
    
    		// If the element is present at the middle itself. 
    		if (arr[mid] == target) {
    			return mid;
    		}
    
    		// If element is smaller than mid, then it can only be present in left subarray 
    		if (target < arr[mid]) {
    			return binary_search(arr, left, mid - 1, target);
    		}
    
    		// Else the element can only be present in right subarray 
    		if (target > arr[mid]) {
    			return binary_search(arr, mid + 1, right, target);
    		}
    	}
    
    	// We reach here when element is not present in array.
    	return -1;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int arr[] = { 2, 3, 4, 10, 40 };
    	int target = 10;
    	int num = sizeof(arr) / sizeof(arr[0]);
    	cout << "sizeof(arr) = " << sizeof(arr) << endl;
    	cout << "sizeof(arr[0]) = " << sizeof(arr[0]) << endl;
    	cout << "target = " << target << endl;
    	int result = binary_search(arr, 0, num - 1, target);
    	(-1 == result) ? cout << "Element is not present in array." << endl : cout << "Element is present at index " << result << "." << endl;
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

## 4. recursive Binary Search ##

Iterative implementation of Binary Search

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    // C++ program to implement iterative Binary Search 
    // A iterative binary search function. 
    // It returns location of x in given array arr[l..r] if present, otherwise -1.
    
    int binary_search(int arr[], int left, int right, int target)
    {
    	while (left <= right)
    	{
    		int mid = left + (right - left) / 2;
    
    		// Check if target is present at mid
    		if (arr[mid] == target) {
    			return mid;
    		}
    
    		// If target greater, ignore left half 
    		if (target > arr[mid]) {
    			left = mid + 1;
    		}
    
    		// If target is smaller, ignore right half 
    		if (target < arr[mid]) {
    			right = mid - 1;
    		}
    	}
    
    	// if we reach here, then element was not present 
    	return -1;
    }
    
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int arr[] = { 2, 3, 4, 10, 40 };
    	int target = 5;
    	int num = sizeof(arr) / sizeof(arr[0]);
    	cout << "sizeof(arr) = " << sizeof(arr) << endl;
    	cout << "sizeof(arr[0]) = " << sizeof(arr[0]) << endl;
    	cout << "target = " << target << endl;
    	int result = binary_search(arr, 0, num - 1, target);
    	(-1 == result) ? cout << "Element is not present in array." << endl : cout << "Element is present at index " << result << "." << endl;
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    // C++ program to implement iterative Binary Search 
    // A iterative binary search function. 
    // It returns location of x in given array arr[l..r] if present, otherwise -1.
    
    int binary_search(int arr[], int left, int right, int target)
    {
    	while (left <= right)
    	{
    		int mid = left + (right - left) / 2;
    
    		// Check if target is present at mid
    		if (arr[mid] == target) {
    			return mid;
    		}
    
    		// If target greater, ignore left half 
    		if (target > arr[mid]) {
    			left = mid + 1;
    		}
    
    		// If target is smaller, ignore right half 
    		if (target < arr[mid]) {
    			right = mid - 1;
    		}
    	}
    
    	// if we reach here, then element was not present 
    	return -1;
    }
    
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int arr[] = { 2, 3, 4, 10, 40 };
    	int target = 10;
    	int num = sizeof(arr) / sizeof(arr[0]);
    	cout << "sizeof(arr) = " << sizeof(arr) << endl;
    	cout << "sizeof(arr[0]) = " << sizeof(arr[0]) << endl;
    	cout << "target = " << target << endl;
    	int result = binary_search(arr, 0, num - 1, target);
    	(-1 == result) ? cout << "Element is not present in array." << endl : cout << "Element is present at index " << result << "." << endl;
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200521221555613.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200521221645626.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200521223934773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200521224012260.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center