[算法][二分法查找]

简介:


 

 

复制代码
 1 /*
 2 二分法实验
 3 1、设a[0:n-1]是一个已排好序的数组.
 4 请改写二分搜索算法,使得当搜索元素x不在数组中时,
 5 返回小于x的最大元素的位置I和大于x的最大元素位置j.
 6 当搜索元素在数组中时,I和j相同,均为x在数组中的位置.
 7 2、设有n个不同的整数排好序后存放于t[0:n-1]中,
 8 若存在一个下标I,0<=i<n,使得t[i]=i,
 9 设计一个有效的算法找到这个下标.
10 要求算法在最坏的情况下的计算时间为O(logn).
11 */
12 #include<iostream>
13 using namespace std;
14 /*
15 功能:1\二分查找改进版
16 输入:拍好序的a[],大小n,待查数x,返回参数i,j
17 返回:真:找到
18 */
19 bool BinarySearch(int *a,int n,int x,int& i,int& j){
20     int left=0;
21     int right=n-1;
22     while(left<=right){
23         int mid=(left+right)/2;
24         if(x==a[mid]){
25             i=j=mid;
26             return true;
27         }
28         if(x>a[mid])
29             left=mid+1;
30         else
31             right=mid-1;
32     }
33     i=right;
34     j=left;
35     return false;
36 }
37 /*
38 功能:2\高效查找
39 输入:数组,大小,待查值
40 返回:下标,若没有返回-1
41 */
42 int SearchTag(int *a,int n,int x){
43     int left=0;
44     int right=n-1;
45     while(left<=right){
46         int mid=(left+right)/2;
47         if(x==a[mid]) return mid;
48         if(x>a[mid])
49             left=mid+1;
50         else
51             right=mid-1;
52     }
53     return -1;
54 }
55 int main(){
56     int n,i,j,a[1000],x;
57     while(cin>>n){//输入数组大小
58         for(i=0;i<n;i++)cin>>a[i];//输入数据,需要从小到大
59         cin>>x;//输入待查数据
60         BinarySearch(a,n,x,i,j);//超找
61         cout<<"用函数1找到的i,j为: "<<'('<<i<<','<<j<<')'<<'\n';//输出对应的i,j
62         cout<<"用函数2找到的下标为: "<<SearchTag(a,n,x)<<"\n\n";//输出2找到的下标
63     }return 0;
64 }
复制代码

 



本文转自beautifulzzzz博客园博客,原文链接:http://www.cnblogs.com/zjutlitao/p/3664896.html,如需转载请自行联系原作者

相关文章
|
算法 搜索推荐 C语言
初阶算法(3):二分法的讲解与实现(C语言),以及二分不止光在有序数组中的应用
初阶算法(3):二分法的讲解与实现(C语言),以及二分不止光在有序数组中的应用
211 0
|
Cloud Native 算法 Go
886. 可能的二分法:图+深度优先算法
这是 力扣上的 886. 可能的二分法,难度为 中等。
|
算法 C语言
【C语言】带你玩转经典算法用二分法在一个有序数组中查找某个数
【C语言】带你玩转经典算法用二分法在一个有序数组中查找某个数
210 0
|
算法 索引
从小白开始刷算法 二分法篇 leetcode.74
从小白开始刷算法 二分法篇 leetcode.74
|
算法 索引
从小白开始刷算法 二分法篇 leetcode.162
从小白开始刷算法 二分法篇 leetcode.162
|
算法 索引
从小白开始刷算法 二分法篇 leetcode.35
从小白开始刷算法 二分法篇 leetcode.35
|
算法 索引
从小白开始刷算法 二分法篇 leetcode.704
从小白开始刷算法 二分法篇 leetcode.704
|
人工智能 算法
【数据结构与算法】数组2:双指针法 & 二分法(螺旋矩阵)
【数据结构与算法】数组2:双指针法 & 二分法(螺旋矩阵)
99 0
|
算法 JavaScript 前端开发
javascript算法之从会用到理解 - 二分法
javascript算法之从会用到理解 - 二分法
121 0
|
算法 索引
数据结构与算法(七) 二分法
数据结构与算法(七) 二分法
79 0