# Algorithm: Binary Search

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).

**I****f** 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).

**r****eturn** -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<=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] < 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 > 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]>=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]<key) return end; if(a[start]<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 > 1 ) { //get middle index mid = start + (end-start)/2; if(a[mid]>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]<=key) return end; if(a[start]<=key) return start; return -1; } } |

What now? How about you solve this codechef problem.

# More from this Category

## Codechef: KMXOR Solution

Codechef May Cook-off 2018: KMXOR editorial with Java implementation.

## Graph Traversal

This article explains breadth first traversal and depth first traversal in graph theory.

## Graph Theory

Terminology and methods to represent a graph are explained.

## Primality Sieves

Segmented Sieve, Sieve of Sundaram, Sieve of Atkin are discussed here.

## Recursion: Optimization

A more optimized approach to the use of recursion

## Recursion vs Iteration

Recursion vs Iteration, which is better? This article will go through pros/cons of iteration and recursion.

## 0 Comments