Homework SourseIn the binary search if the array being searched has 32 elem
In the binary search, if the array being searched has 32 elements in it, how many elements of the array must be examined to be certain that the array does not contain the key? What about 1024 elements? Note: the answer is the same regardless of whether the algorithm is recursive or iterative.
Solution
Binary Search Algorithm- Fundamentals, Implementation and Analysis
Hitesh Garg | May 15, 2015 | algorithms | 5 Comments
Binary Search Algorithm and its Implementation
In our previous tutorial we discussed about Linear search algorithm which is the most basic algorithm of searching which has some disadvantages in terms of time complexity, so to overcome them to a level an algorithm based on dichotomic (i.e. selection between two distinct alternatives) divide and conquer technique is used i.e. Binary search algorithm and it is used to find an element in a sorted array (yes, it is a prerequisite for this algorithm and a limitation too).
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)
So the idea is-
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;
}
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;
}
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\");
}
}
}
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.
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.
| 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) } |
