Binary search algorithm and it is
used to find an element in a sorted array
In this algorithm we use the sorted
array so as to reduce the time complexity to O(log n). In this, size of the
elements reduce to half after each iteration and this is achieved by comparing
the middle element with the key and if they are unequal then we choose the
first or second half, whichever is expected to hold the key (if available)
based on the comparison i.e. if array is sorted in an increasing manner and the
key is smaller than middle element than definitely if key exists, it will be in
the first half, we chose it and repeat same operation again and again until key
is found or no more elements are left in the array.
Recursive
Pseudocode:
|
1
2
3
4
5
6
7
8
9
10
11
12
|
// initially called with low = 0, high = N – 1
BinarySearch_Right(A[0..N-1], value, low,
high) {
// invariants: value
>= A[i] for all i < low
value
< A[i] for all
i > high
if (high < low)
return low
mid = low +((high –
low) / 2) // THIS IS AN IMPORTANT STEP TO AVOID BUGS
if (A[mid] > value)
return BinarySearch_Right(A, value, low,
mid-1)
else
return BinarySearch_Right(A, value,
mid+1, high)
}
|
Iterative
Pseudocode:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
BinarySearch_Right(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
//
invariants: value >= A[i] for all i < low
value
< A[i] for all
i > high
mid
= low +((high – low) / 2) // THIS IS AN IMPORTANT STEP TO AVOID BUGS
if (A[mid] > value)
high
= mid - 1
else
low
= mid + 1
}
return low
}
|
Asymptotic Analysis
Since this
algorithm halves the no of elements to be checked after every iteration it will
take logarithmic time to find any element i.e. O(log n) (where
n is number of elements in the list) and its expected cost is also proportional
to log n provided that searching and comparing cost
of all the elements is same
Data structure used -> Array
Worst case performance -> O(log n)
Best case performance -> O(1)
Average case performance -> O(log n)
Worst case space complexity -> O(1)
Worst case performance -> O(log n)
Best case performance -> O(1)
Average case performance -> O(log n)
Worst case space complexity -> O(1)
So the idea is-
1.
Compare the key (element to be searched) with the mid element.
2.
If key matches with middle element, we return the mid index.
3.
Else If key is greater than the mid element, then key can only
lie in right half subarray after the mid element. So we recur for right half.
4.
Else (x is smaller) recur for the left half until there are no
more elements left in the array.
RECURSIVE Implementation
of Binary search in C programming language
|
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
|
#include <stdio.h>
// A recursive binary search function. It returns location
of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if
(r >= l)
{
int mid = l + (r - l)/2;
// If the
element is present at the middle itself
if (arr[mid] == x) return mid;
// If
element is smaller than mid, then it can only be present
// in left
subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
// Else
the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not
present in array
return
-1;
}
int main(void)
{
int
arr[] = {2, 3, 4, 5, 10, 15, 25, 40};
int
n = sizeof(arr)/ sizeof(arr[0]);
int
x = 15;
int
result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is
not present in array")
:
printf("Element is present at index %d", result);
return
0;
}
|
Output:-
Element is present at index 5
ITERATIVE Implementation
of Binary search in C programming language
|
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
|
#include <stdio.h>
// A iterative binary search function. It returns location
of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while
(l <= r)
{
int
m = l + (r-l)/2;
if
(arr[m] == x) return
m; // Check if x is present at mid
if
(arr[m] < x) l = m + 1; // If x greater, ignore left
half
else
r = m - 1; // If x is smaller, ignore right half
}
return
-1; // If this line executes, then search was unsuccessful
i.e. element is not present
}
int main(void)
{
int
arr[] = {2, 3, 4, 5, 10, 15, 25, 40};
int
n = sizeof(arr)/ sizeof(arr[0]);
int
x = 15;
int
result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is
not present in array")
:
printf("Element is present at index %d", result);
return
0;
}
|
Output:-
Element is present at index 5
Implementation of
BinarySearch(Iterative and Recursive methods) in Java
In Java Binary
Search method is already implemented and it is recommended that we should
use java.util.Arrays.binarySearch(//A lot of overloaded functions). See complete list
of functions here – Oracle – java.util.Arrays
|
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
|
package com.codingeek.algorithms;
public class RecursiveBinarySearchAlgorithm {
public static int
recursiveBinarySearch(int[] sortedArray, int start, int end, int key) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return recursiveBinarySearch(sortedArray,
start, mid, key);
}
else if (key > sortedArray[mid]) {
return recursiveBinarySearch(sortedArray,
mid+1, end , key);
}
else {
return mid;
}
}
return -1;
}
public static void
main(String[] args) {
int[] arr1
= {2,45,100,190,280,500,670,700,999};
int index =
recursiveBinarySearch(arr1,0,arr1.length,45);
if(index
!= -1){
System.out.println("Found
45 at "+index+" index");
}
else{
System.out.println("Element
not found");
}
index =
recursiveBinarySearch(arr1,0,arr1.length,99);
if(index
!= -1){
System.out.println("Found
999 at "+index+" index");
}else{
System.out.println("Element
not found");
}
}
}
|
Output:-
Found 45 at 1 index
Element not found
IMPORTANT NOTE :- One important
point was that while finding the mid-point we do (mid = low +((high – low) /
2)) while this can also be achieved by simply doing (mid =(high + low) / 2)).
This is because if both the numbers i.e. low and high are too high such that
their sum reaches above the range of datatype used then it will produce an
error as it will become a negative number and no array index of negative value
is possible.
For ex – if low =
32,000 and high = 32,700 then
mid = (32000 + 32700)/2 = 64700/2
In C Language => 64700 for an “int” type is equal to (-835)
i.e. (-835)/2 = (-417), which will produce error.
mid = (32000 + 32700)/2 = 64700/2
In C Language => 64700 for an “int” type is equal to (-835)
i.e. (-835)/2 = (-417), which will produce error.
So to avoid such situations we add
the half of difference between the two to the lower value which ensures that we
never encounter such a situation.
No comments:
Post a Comment