`

二分查找之变型题目

阅读更多
二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就可以看出来的二分查找。
我见过的一些变型,一种是有序的环形队列,不知道队头,另一种是有序数组循环移动得到的数组,这种变型无非是多绕了一个弯,多一次查找,首先二分查找到队头,最小元素/最大元素,然后再二分查找指定的元素。
#include <iostream>
#include <cstdlib>

/*
 * Author: fuliang http://fuliang.iteye.com
 * 二分查找分界点,最小值的index
 */
int binary_search_min(int a[],int n){
	if(n <= 0) return -1;
	if(a[0] < a[n-1]) return 0;//递增有序序列
	int b = a[0];
	int i = 0,j = n-1;
	int mid;
	while(i < j){
		mid = (i  + j) / 2;
		if( a[mid] >= b ){
			i = mid+1;
		}else {
			j = mid;
			b = a[mid];
		}
	}
	return i;
}

int cmp(const void *x, const void *y){
	 return ( *(int *)x - *(int*)y );
}
/*
 * 根据分界点二分查找
 */
int * bin_search(int x,int a[],int n,int m_index){
	if(a[n-1] >= x){
		return (int *)bsearch(&x,a+m_index,n-m_index,sizeof(int),cmp) ;
	}else{
		return (int *)bsearch(&x,a,m_index,sizeof(int),cmp) ;
	}
}

int main(){
	int a[] = {4,5,6,7,8,1,2,3};
	int m_index = binary_search_min(a,8);
	int *target_addr = bin_search(6,a,8,m_index) ;
	if(target_addr){
		std::cout << "Min index: " << m_index << " and result index: " << target_addr - a << std::endl;
	}else{
		std::cout  << "Not find" << std::endl;
	}
}
分享到:
评论

相关推荐

    zoj题目简单归类zoj题目简单归类

    题目要求已知两数之和与差,求出这两个数。这通常是一个基础的代数问题,可以通过建立方程组来求解。 #### #2405 Property List 题目要求列出某个范围内满足特定性质的数。解决策略通常是通过枚举范围内的所有数,...

    leetcode卡-leetcode_practices_learncard_binarysearch:我的leetcode实践二分搜索学习卡

    - **变形二分查找**:如`33. 搜索旋转排序数组`,数组在某点进行了旋转,需要先确定旋转点再进行二分。 - **二分查找应用**:例如`153. 寻找旋转排序数组中的最小值`,在已知数组为旋转数组的情况下找到最小值。 - *...

    最低加油次数leetcode-Leetcode:力码

    两指针o(n)遍历变形二分查找,第一个数组找cut点,第二个数组的cut点位置可以计算得到 TOP 1、扩充法,从mid向两边遍历2、马拉车算法 TODO马拉车算法 TOP unsigned int 判断溢出的小trick TOP 两端向中间逼近找答案 ...

    阿里技术《程序员面试宝典》

    3. **二分查找**:不仅介绍了基础的二分查找算法,还讨论了其在区间查询、存在性查找、最值查找等问题中的应用,并探讨了如何在链表、有序集合等数据结构上进行二分查找。 4. **数组**:涵盖了一维、二维数组的处理...

    leetcode官方50题算法详解

    这些题目按照不同数据结构或算法分类,如数组/字符串、数学、链表、二叉树、位运算、杂项、栈、动态规划、二分查找等,并提供了详细的算法说明和题目解答。下面对这些类别和其中一些典型题目进行详细的知识点说明: ...

    算法设计与分析复习题目及答案1

    1. 二分搜索算法:二分搜索是一种基于分治策略的算法,它在已排序的列表中查找目标值,通过不断将搜索区间减半来快速定位目标。 2. 动态规划算法基本步骤:动态规划是一种用于求解最优化问题的方法,其基本步骤包括...

    算法分析复习题目及答案80.doc

    二分搜索算法利用了分治策略,通过不断将查找区间减半来快速定位目标元素。 2. 动态规划算法的基本步骤不包括哪个? 动态规划算法的基本步骤包括:找出最优解的性质、定义最优解、构造最优解和计算最优解,不包括...

    算法分析复习题目及答案8.doc

    二分搜索算法就是典型的分治策略应用,它通过不断将查找区间减半来定位目标元素。 2. **动态规划**:动态规划用于解决具有重叠子问题和最优子结构的问题,通过构建子问题的最优解来组合成原问题的最优解。题目中...

    南京市小学生信息学竞赛初赛复习 知识要点复习进程.docx

    1. **二分查找**:二分查找是一种在有序数组中查找特定元素的搜索算法。通过不断将查找区间折半,快速定位目标值,其时间复杂度为O(logn)。 2. **循环数组**:循环数组是数组的一种特殊形式,数组的末尾与开头相连...

    C语言程序设计\2008年9月计算机等级考试二级C++真题含答案.pdf

    - **题目解析**:此题考察了二分查找算法的时间复杂度。二分查找算法适用于有序数组,通过不断将搜索区间减半来提高查找效率。 - **选项分析**: - A选项:O(n)代表线性时间复杂度,适用于遍历整个数组; - B...

    ACM题库完整版.pdf

    二分查找、快速排序等都是分治算法的典型应用。 数学类题目也是ACM竞赛中不可或缺的一部分,包括: 1. 数论:涉及素数的判定、求解最大公约数、最小公倍数、同余问题等。题目可能要求选手使用欧拉函数、费马小定理...

    Thesis2013-浅谈数据结构题的几个非经典解法1

    文中可能涉及了二分查找的变形或在解决特定数据结构问题时的应用。 6. **贪心算法(Greedy Algorithm)**:在每一步选择局部最优解,期望全局最优。文章中可能讨论了如何在数据结构问题中使用贪心策略来找到解决...

    候选消除算法 机器学习实验

    - 性能优化,如使用二分查找替换顺序查找,或者利用并行计算加速比较和消除过程。 通过这个实验,你可以深入理解候选消除算法的工作原理,并掌握在实际编程中如何处理大型数据集。同时,你还能锻炼到文件操作、数据...

    华为机试108题源码(题目&&解答)

    ├─053 查找整数二进制中1的个数 ├─054 DNA子串 ├─055 MP3光标位置 │ └─Source │ └─Debug ├─056 查找2个字符串最大相同子串 │ └─Debug ├─057 配置文件恢复 │ └─Source │ └─Debug ├─058 24...

    蓝桥杯真题

    例如,快速排序的优化版本,二分查找的变形等,同时引入了图论中更复杂的最短路径问题,以及树的遍历等数据结构相关的题目。 而“第三届蓝桥杯本科省赛真题”对于编程初学者来说是个好开始。这些题目虽然难度较低,...

    面试常考算法必刷题库1

    5. **木材加工**:这类问题通常涉及排序和二分查找算法,以优化木材的切割方案。 6. **最多有k个不同字符的最长子字符串**:找到一个字符串中最长的子字符串,其中最多包含k个不同的字符。这可能需要滑动窗口和哈希...

    数据结构1800

    11. **排序与查找**:排序算法如冒泡排序、快速排序、归并排序等,查找算法如顺序查找、二分查找、哈希查找等,是数据结构的基础,也是实际编程中经常用到的技巧。 1800道题目中,可能会覆盖以上所有知识点,并可能...

    和为s的两个数1

    4. **二分查找变种**:双指针法可以视为有序数组上的二分查找的一种变形。 5. **条件分支**:在代码中使用if语句进行条件判断,控制程序流程。 6. **向量操作**:在C++中使用`vector`容器存储和返回结果,了解其基本...

    刷题笔记1

    3. **二分搜索**:在有序数组中快速查找元素或解决问题的技术,如查找元素、搜索插入位置、计算阶乘函数后的K个零等。 4. **链表**:不同于数组,链表中的元素不连续存储,而是通过节点间的指针连接。链表题目包括...

    算法设计与分析复习题目及答案1.doc

    例如,二分搜索算法就是通过不断将搜索区间减半来查找目标元素,属于分治策略的典型应用。选项A是正确的。 2. 动态规划算法用于解决具有重叠子问题和最优子结构的问题,如最长公共子序列、背包问题等。动态规划的...

Global site tag (gtag.js) - Google Analytics