Binary search algorithm

January 4, 2018

Introduction

In terms of search efficiency, the binary search will be much more efficient compared to linear scan.
Last 6 months I have practiced so many binary search with so many peers, write a few blogs related to the issues I have.

After the mock interview, I have some short discussion about binary search algorithm again.

Repetitions

It is the best time for me to discuss the algorithm with the peer. Here is the algorithm.

Here is the question link.


Problem statement: Given 2 vectors with multiple repetitions, calculate dot product, and create a data structure.
For example, two vectors:   [2, 1, 1, 1] , [2, 1, 1, 1], and the dot product is [2 *2, 1* 1, 1 * 1, 1 * 1].

The peer shared his original idea to design a structure like the following:

[2,1 (a million times)]

In c, the problem can be written in the following:
typedef struct pair{
  int value;
  int amount;
}Pair;

int dotProduct(Pair v1[], Pair v2[]){
 // write this function
}


Instead I gave my thought, given start and end index of repetitive number, so binary search can be applied to do
the index search. Otherwise, the peer's data structure the array search will be linear scan.

[1, 2, 1000,000, 100,000 + 1] -> binary search ->
[(1,2), (million, 1)] <- new data structure (1, 2), (2, 1), ..., (1000,000, 1)

If the number is not in the array, just return the value next smaller or bigger index with value.