# Binary Search from a different perspective

Ever wondered how useful binary search can be for solving different problems? This blog will discuss binary search from a different perspective, not just searching in the sorted array.

Let’s understand this by walking through the below problem.

You can find the problem here.

Given an array of integers nums containing n + 1 integers where each integer is in the range`[1, n]`

inclusive. There is only one repeated number in nums. Return this repeated number. You must solve the problem without modifying the array nums and using only constant extra space.

It’s indeed non-intuitive to think of this problem from the perspective of binary search. Because we don’t have a sorted space to apply it, and if we think of sorting the given array, it would violate the condition not to modify the array. So, let’s examine the problem more deeply and justify our binary search approach.

Although the elements in the array are not sorted, they all lie in a [1,n] indirectly if we can see that all natural numbers, whole numbers, and integers are, by default, defined in a sorted way. **So we can perform binary-search on the natural numbers instead on the array elements.**

This is a frequent idea that is used to solve many medium and hard-level data-structure problems. You can always give a try to binary search whenever you see elements are in a fixed interval.

So now we have clear boundaries of the interval for starting binary search. But on what basis do we search? Is it by comparing the numbers? Or some other property? This brings me to the second part of the article. A special property(often underlooked) of natural numbers.

In the given problem, although we can have a maximum of n distinct natural numbers, the array is of the size of n+1, which means there will be at least one repeated number (also called the pigeonhole principle). Ok assume the numbers 1,2,3 ….n. How many numbers will be there that are less than or equal to 3? Three right? How many numbers are smaller or equal to 10? Ten right? But what if 2 is repeated two times? What is the count of numbers that are smaller or equal to 3? 4, which is greater than 3 itself.

That’s it; we have found a property to find the duplicate number. For each number n, if no repeated elements are lesser than it, there will be n elements lesser than n. If any repeated number is smaller than it, the count will be greater than n.

Let’s see how it translates into code: We have initialized two pointers with st=1 and en=n as they are the boundaries. Now we take a number mid and check whether any repeated numbers are lesser than mid. If there count is lesser than mid, then there is a number greater than mid, making the limited size of the array insufficient for numbers lesser than mid. So we move pointer *st* to *mid+1.* If the count is equal to mid, nothing is repeated under mid so we will move the pointer again to *mid+1.* Else we move it *en* to *mid*. Why not *mid-1*? There is a possibility that mid itself is a repeating number so that we will move *en* to mid instead of *mid-1*.

```
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n=nums.size();
int st=1,en=n;//range [1,n]
while(st<en){
int mid=(st+en)/2;
int count=0;
//checking the number of elements in
//the whole array that are lesser than mid.
for(int i{};i<n;i++){
if(nums[i]<=mid){
count++;
}
}
if(count<=mid){
st=mid+1;
}else{
en=mid;
}
}
//st==en==mid
return st;
}
};
```

*Thank you for reading the article. Give a clap if you like it.*