二分查找算法的一点改进
在计算机科学中，二分查找，是一种在有序数组中查找某一特定元素的搜索算法。这种搜索算法每一次比较都使搜索范围减半。第一篇二分查找的论文发表于1946年，然而第一个没有bug的二分查找算法却是在1962年才出现，中间用了16年时间。
本文首先二分查找算法给出了官方标准写法，然后给出另两种改进。主要原因是，当low和high对应的数组元素比较大时，求平均值可能会造成溢出，所以针对此做了一些改进。下面是相关代码实现。
//description: 给出二分查找法的几种C语言实现方法,其中第一种是官方写法，其它两种是改进
//compile：gcc -g binary_search.c -o binary_search
//date： 2019-04-30#include int binary_search_v1(int a[], int n, int k){int low, high, mid;low = 0;high = n-1;while(low <= high){mid = (low+high)/2;if(ka[mid])low = mid+1;elsereturn mid;}return -1;
}int binary_search_v2(int a[], int n, int k){int low, high, mid;low = 0;high = n-1;while(low <= high){//这里当low和heigh很大时，避免溢出mid = low+(high-low)/2;if(ka[mid])low = mid+1;elsereturn mid;}return -1;
}int binary_search_v3(int a[], int n, int k){int low, high, mid;low = 0;high = n-1;while(low <= high){//这里使用位运算效率更高mid = low+((high-low)>>1);if(ka[mid])low = mid+1;elsereturn mid;}return -1;
}int main() {int arr[] = {1,3,45,78,200,213,455};int size = sizeof(arr)/sizeof(int);int key = 213;int result1 = binary_search_v1(arr, size, key);int result2 = binary_search_v2(arr, size, key);int result3 = binary_search_v3(arr, size, key);printf("binary search result: %d, %d, %d
", result1, result2, result3);return 0;
}
运行截图如下：
参考文献
[1].https://www.toutiao.com/a6685490937977635341/
更多相关：
-
Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。 我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...
-
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...
-
利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...
-
题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...
-
题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树： 5 / 2 6 / 1 3示例 1： 输入: [1,6,3,2,5] 输出...
-
问题描述： 给定一个排序数组nums(nums中有重复元素)与目标值target，如果 target在nums里出现，则返回target所在区间的左右端点下标，[左端点, 右端点]，如果target在nums里未出现，则返回[-1, -1]。 例如: arr = [2,3,4,4,4],target = 4,最终结果为[2,4] a...
-
问题描述： 给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里 出现，则返回target所在下标，如果target在nums里未出现，则返回target应该 插入位置的数组下标，使得将target插入数组nums后，数组仍有序。 例如： 数组 arr = [2,3,4,6] target = 1...
-
75. Find Peak Element 【medium】 There is an integer array which has the following features: The numbers in adjacent positions are different.A[0] < A[1] && A[A.length...
-
题目： Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt...
-
有序表查找 /* 主函数 */public class OrderTableSearch {public static void main(String[] args) {int [] a= {0,1,16,24,35,47,59,62,73,88,99}; System.out.println(FibonacciSearc...
-
割点：去掉某点x，该无向图分割成两部分（及以上） 割边：去掉某条边x，该无向图分割成两部分（及以上） 时间戳：在搜索树上的遍历序号dfn 追溯值：subtree子树和非搜索树上可达的最小点 割边和割点判定 1 void tarjan(int x, int in_edge) { 2 dfn[x] = low[x] = ++...