Binary Search Assignment Help

1. What is a Search Algorithm?

It is an algorithm that is used to retrieve information stored within data structure like Arrays, linked lists, search trees, stacks, queues etc. The appropriate algorithm depends on the type of data structure being searched. They can be classified based on their mechanism of searching. For example,

Linear search algorithms checks each and every value linearly, starting from the beginning element.
Binary(half interval searches), repeatedly compares the middle element of the structure and with each step, it divide the search space in half.
Comparison search algorithm is an improvisation on linear search algorithm because it successively eliminates the records which are produced by the comparisons of the keys, until the target record is found, Thus, it can be applied on data structures with a defined order.
Digital search algorithms mainly based on the properties of digits in data structures.

2. Difference between Linear Search and Binary Search Algorithm

Linear search starts at the beginning of data structure and checks each value until it get the target value whereas In binary search, the starting point is the middle of a sorted list and determines which side is the target value. Even in terms of time complexity, Binary search is better than linear search. The time complexity for worst case in Binary search is O(log n) whereas in Linear search, it is O(n). But, we can perform binary search only in sorted list of items.

3. Binary Search Introduction

Binary Search is an efficient search algorithm that finds the target value from an ordered list. It compares the target value to the middle element of the list. If they are not equal, then the half portion of list is eliminated in which the target value cannot lie and it repeatedly divides the remaining half until it finds the desired value. Binary search is based on divide and conquer strategy to find a value within a list which is already sorted. In next section, we’ll briefly explain Divide and Conquer strategy in algorithms.

Binary Search Assignment Help By Online Tutoring and Guided Sessions from AssignmentHelp.Net

3.1 Divide and Conquer algorithm

Divide and Conquer is a powerful tool for solving sophisticated problems. The main idea is to break down a problem recursively into two or more sub problems, until it becomes easy enough to be solved directly. And then, the solution to the sub problems are combined to produce a solution to the original problem. For understanding Divide and Conquer algorithm, you need to understand the nature of the problem to be solved. In case of Binary Search Algorithm, Divide and Conquer strategy applied in the form of dividing a problem into only one sub-problem. In this case, it is more efficient algorithm as compared to the general divide and conquer algorithm. The important application of Divide and Conquer algorithm is in Prune and Search, it is a method of solving optimization problems. In prune and search, at each step, the search space is pruned by a constant factor, the algorithm has the same complexity as the pruning step and the constant depends on the pruning factor.

4. Binary Search Algorithm

The main requirement for Binary Search is that the array being already sorted.

1. We have an array ‘A’ of size, N and ‘x’ is the target value.
We’ll define two variable, ‘low’ being the lowest position of array and ‘high’ being the highest position of array.
low=0
high=N-1
And the middle position is, mid= (low + high)/2

2. If A[mid]=x, done

3. Else if, A[middle]>x, eliminate the second half that is from A[mid+1] to A[high]
Now, low=0
high=mid-1
Find mid and compare x with A[mid]. If equal then you are done, else
Eliminate the half portion where the value cannot lie.

4. Repeat it, until you get the value.

5. Binary Search Pseudocode

Binary Search can be done Iteratively as well as recursively.

First, the Recursive Pseudocode

{`
//low=0, high=N-1
Binary_Search(A[N-1] , x, low, high){
if(high < low)
return not_found
mid=(low+high)/2
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid
}
Iterative Pseudocode
BinarySearch(A[0..N-1], value) {
low = 0
high = N – 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid – 1
else if (A[mid] < value)
low = mid + 1
else
return mid
}
return not_found
}
`}

6. Binary Search algorithm example

Now, We’ll explain it with an example.67
Let’s take an array,
The values written above array are index of the corresponding items.

As, we explained earlier, low represents the lowest index and high gives the highest index of array. N represents the size of array and x denotes the value we want to search in the array.

{`
Here low=0
high=8 and N=9 and x=44
mid=(low+high)/2=4
`}

1. A[mid]=30,
Now , we’ll compare the value in index ‘mid’ with ‘x’.
Since, 30<44. So
Eliminate the first half. That’ll make the value of low 5 that is mid+1, keeping the value of high same.

2. A[mid]=67
We are again comparing the value in index ‘mid’ with ‘x’.
67 >44,
Eliminate the portion from mid+1 to high. That’ll make the value of high 5, keeping the value of low same.
Therefore,

3. A[mid]=44, which is equal to target value.
So, the position of target value is 5.

7. Binary Search Code in Java

{`
import java.util.Scanner;
Class Binary
{
Public static void main(String args[])
{
Int N,x, Arr[],low,high,mid;
Scanner in = new Scanner(System.in);

System.out.println(“Enter the size of array”);

N = input.nextInt();
Arr = new int[N];

System.out.println(“Enter ” +  N + “ integers”);
for(int count : Arr)
{
Arr[count] = in.nextInt();
}
System.out.println(“Enter the value you want to search”);
x=in.nextInt();
low=0;
high=N-1;
mid=(low+high)/2;

while(low <= high)
{
If(Arr[mid] == x)
{
System.out.println( x  + “found at location” + mid + “.”);
Break;
}
else if(Arr[mid]>x)
{
high=mid-1;
}
else
{
low=mid+1;
}
mid=(low+high)/2;
}
if(low> high)
{
System.out.println(x + “not found\n”);
}
}
}
`}

8. Binary Search Code in C

{`
#include
Int main()
{
int N,x, low, high, mid, count,  Arr[50];
printf(“Enter the number of elements\n”);
scanf(“%d” , &N);
printf(“Enter %d integers\n”,N);
for(count=0;count < n; count++)
{
Scanf (“%d,&Arr[count]);
}
printf(“Enter the value you want to search:\n”);
scanf(“%d”,&x);

low=0;
high=N-1;
mid=(low+high)/2;

while(low <= high)
{
if(Arr[mid] == x)
{
System.out.println( x  + “found at location” + mid + “.”);
break;
}
else if(Arr[mid]>x)
{
high=mid-1;
}
else
{
low=mid+1;
}
mid=(low+high)/2;
}
if(low> high)
{
printf(“%d not found”,x);
}

return 0;
}
`}

9. Complexity of Binary Search

Suppose we have an array A and we are searching ‘x’ in this array, if it is not sorted then we have to perform linear search and that ‘ll take O(n) time. But if A is a sorted array, there is a much faster way, that is Binary Search.

The analysis of binary search can be done in three type of comparisons. These are best case, worst case and average. Let N be the size of array A. Binary Search as we discussed earlier can be performed recursively as well as iteratively and in both the cases, the number of comparisons are same.

Now, we’ll explain all the three cases of comparisons.

Best case: The time complexity of best case is O(1). This is called Big O Notation. In this case, the value we are searching is the middle in the array. So only one comparison is needed for finding it. Thus, the time complexity is O(1).

Worst Case: Generally, when we analyse the time complexity of any algorithm, it is given by its worst case. That is why, the time complexity of binary search algorithm belongs to O(log n) class. It represents that the asymptotic growth of time the function is taking to execute when an input size ‘n’ is given will not be greater than log n. In this case, the item does not exist at all.

Now for the average case,

Average case: We’ll first calculate the number of comparisons that are required to find each element and the probability of searching for that element and then doing the sum over the product of the above two entities we calculated. To simplify this, we assume that we are not taking the case in which the value we are searching is not in array and the probabilities of searching each element is uniform.

Now, let’s talk about the difference between O(log(N)) and O(N):

This difference became extremely significant when N is large.

For example, suppose the array contains 2 billion values. Linear search would require about a billion comparisons whereas binary search can do it in only 32 comparisons.

{`
Mathematically,
We can calculate the time complexity using the recurrence relation,
For Binary Search, it is
T(N) = T(N/2) + O(1)
T(N/2)= T(N/4) + 1 +1
Putting the value of T(N/2) to the above relation giving:
T(N) = T(N/4) + 1 +1…… T(n/2^k)+1+1+1…+1
=T(2^k/2^k)+1…+1 up to k
=T(1)+1
As we take 2^k=n
K=log n
`}