Algorithm: Binary Search

by | Mar 1, 2018

Yolo ppl! This post will be about binary search method ( works only on sorted arrays ). After the theoretical stuff, I’ll dive into some applications of binary search to find floor and ceils.

Why the gap in posts? Well, I participated in ACM ICPC Prelims for the first time and didn’t qualify;_;… Learnt Segment Tree, prepared for Google Summer of Code 2018, yeah it is going on right now… more on that later.

How to find index of an element K in a given array

using Binary Search?

Binary Search is a much faster algorithm O(log n) as compared to Linear Search O(n). The only drawback is that the array must be already sorted, in non-increasing or non-decreasing order.

The algorithm is used to find the index of K in the array. We select a range in the array where there is a possibility that K exists in it and compare K with the value at the MIDDLE of the range. Next, we trim the range according to compare results and continue until the range has just one element remaining.

Algorithm

The following algorithm assumes that the array is sorted in non-decreasing order.

Let MID refer to the element lying at center of range [START, END] and

MID_INDEX be the index of MID ( (START+END)/2 ).

Create a range with indexes START and END of the array.

While the range length is greater than 1 (START < END):

If MID is equal to K, return MID_INDEX

If MID is smaller than K, trim range to [START, MID_INDEX-1]

This is because it is certain that K cannot lie beyond MID_INDEX (array is already sorted).

If MID is greater than K, trim range to [MID_INDEX+1, END]

This is because it is certain that K cannot lie before MID_INDEX (array is already sorted).

return -1 if the K could not be found.

We are jumping elements(trimming the range) by a factor of 2 at each iteration. The complexity, therefore, becomes log2 N or eventually O(log N).

Implementation ( Java )

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
class BinarySearch
{
public static void main(String args[])
{
int[] a={0,1,2,3,4,5,6,7,8,9,10};
System.out.println(binarySearch(a, 4));
}
static int binarySearch(int[] a, int key) {
int start = 0,
end = a.length-1,
mid;
while(start&lt;=end) {

//get middle index
mid = start + (end-start)/2; //prevents overflows

//If element is found
if(a[mid] == key)
return mid;

//If element is expected in the right half
else if(a[mid] &lt; key)
start = mid+1;

//If element is expected in the left half
else
end = mid-1;
}
return -1;
}
}

 That’s not all.. this algorithm can be modified to find:

    • Greatest/Smallest number smaller than K

    • Greatest/Smallest number smaller than or equal to K

How about you give it a try before reading on? 🙂 

 

How to find the index of a number smaller than K in

a given array using Binary Search?

Algorithm

The following algorithm assumes that the array is sorted in non-decreasing order.

Let MID refer to the element lying at center of range [START, END] and

       MID_INDEX be the index of MID ( (START+END)/2 ).

Create a range with indexes START and END of the array.

While the size of Range is greater than 1:

        If MID is greater than or equal to K, trim range to [START, MID-1]

Here, we can assume that MID is the greatest or equal to K we’ve found so far. Hence, our target element must lie between START and MID-1.

else trim range to [MID, END]

Here, we may presume MID to be our target element. However, there’s a possibility of a greater element to exist between MID and END.

In the end, we have to indexes where there is a possibility of finding the floor: START and END.

 

 

Implementation ( Java )

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
class BinaryStrictFloor
{
public static void main(String args[])
{
int[] a={10,11,12,13,14,15,16,17,18,19,110};
System.out.println(binaryStrictFloor(a, 14));
}
static int binaryStrictFloor(int[] a, int key) {
int start = 0,
end = a.length-1,
mid;
//We exit search when range size becomes less than 2
//in order to avoid getting stuck in an infinite loop...
//in that case (low+high)/2 will give us low
while( end-start &gt; 1 ) {
//get middle index
mid = start + (end-start)/2; //prevents overflows
//Since we need to find greatest number smaller than KEY,
//Trim range from end if a[MID] is greater than equal to KEY.
if(a[mid]&gt;=key)
end = mid-1; // New search range will be [START, MID-1]
//Otherwise, we trim range from START
else
start = mid; //New search range will be [MID_INDEX, END]
}
//We check a[end] first.. since we need the greatest element
if(a[end]&lt;key)
return end;
if(a[start]&lt;key)
return start;
return -1;
}
}

How to find the index of a number smaller than or

equal to K in a given array using Binary Search?

 

Algorithm

The following algorithm assumes that the array is sorted in non-decreasing order.

Let MID refer to the element lying at center of range [START, END] and

       MID_INDEX be the index of MID ( (START+END)/2 ).

Create a range with indexes START and END of the array.

While the size of Range is greater than 1:

If MID is greater K, trim range to [START, MID-1]

Here, we can assume that MID is the greatest K we’ve found so far. Hence, our target element must lie between START and MID-1.

else trim range to [MID, END]

Here, we can assume MID to be our target element. However, there’s a possibility of a greater element to exist between MID and END.

In the end, we have to indexes where there is a possibility of finding the floor: START and END.

 

 

Implementation ( Java )

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
class BinaryFloor
{
public static void main(String args[])
{
int[] a={10,11,12,13,14,15,16,17,18,19,110};
System.out.println(binaryFloor(a, 14));
}
static int binaryFloor(int[] a, int key) {
int start = 0,
end = a.length-1,
mid;
//We exit search when range size becomes less than 2
//in order to avoid getting stuck in an infinite loop...
//in that case (low+high)/2 will give us low
while( end-start &gt; 1 ) {
//get middle index
mid = start + (end-start)/2;
if(a[mid]&gt;key)
end=mid-1; //Trim range to [START, MID_INDEX-1]
else
start=mid; //Trim range to [MID_INDEX, END]
}
//We check a[end] first.. since we need the greatest element
if(a[end]&lt;=key) return end;
if(a[start]&lt;=key) return start;
return -1;
}
}

What now? How about you solve this codechef problem.

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

More from this Category