-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search.c
More file actions
54 lines (53 loc) · 1.49 KB
/
binary_search.c
File metadata and controls
54 lines (53 loc) · 1.49 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
* =========================================================
* Filename: binary_search.c
* Description: Given a sorted array arr[] of n elements, write a
* function to search a given element x in arr[].
*
*
* =========================================================
*/
#include <stdio.h>
int search(int arr[],int n ,int x); // O(N)
int bin_search(int arr[],int n,int x);// Iterative O(log(N))
int bin_search_r(int arr[],int left , int right ,int x);// Recursive
int main(){
int arr[] = {2,3,4,10,20,43};//sorted array
int n = sizeof(arr)/sizeof(arr[0]);
int x = 10;
int index = bin_search(arr,n,x);
(index == -1)?printf("elem not in array\n"):printf("elem index is %d\n",index);
}
int search(int arr[],int n ,int x){
int i;
for(i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int bin_search(int arr[],int n,int x){
int left = 0;
int right = n - 1;
int mid;
while(left <= right){
mid = left + (right - left)/2;
if(arr[mid] == x)
return mid;
else if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int bin_search_r(int arr[],int left , int right ,int x){
if(left > right)
return -1;
int mid = left + (right - left)/2;
if(arr[mid] == x)
return mid;
else if(arr[mid] < x)
return bin_search_r(arr,mid + 1,right ,x);
else
return bin_search_r(arr,left,mid - 1,x);
}