# Binary Search Fundamentals

Get started**🕉**

# জয় শ্রী রাম

If you already know the basics of

*, feel free to skip to the next chapter Advanced Binary Search.*

**Binary Search****is a very intuitive algorithm and I will show you how intuitive it is by giving an example. Say, you are teaching assistant for a class of 100 students who have**

*Binary Search***Student IDs**ranging from 1 to 100. The students appeared in their midterm exam and now they have been notified that their scores are out and they can visit the teaching assistant and take a look at their paper. The teaching assistant has arranged the students' papers in the ascending order of the

*Student IDs*. Now say the student whose student id is 75 shows up and now you have to search his paper and hand that over to him so that he can see how his paper has been graded. If you are the teaching assistant you probably wouldn't go through all the papers sequentially from 1 to 75 to get the paper for the student with student id 75. What you would probably do is open the stack of papers to roughly through halfway (comparable to

`mid`

in our code) through the papers and compare it. Let's suppose,
you saw that the student id was 50. You know that 75 comes after 50, so it must be in the second half of the stack.
So you take the second half of the stack (from student id 51 to 100 ) and treat it as its own little stack and repeat what you did before.
You picked up a paper which is roughly around midway and see what it's student id is and bingo it's 75. We would do the same thing
in our *and it will be clear in a minute when we look at its code below:*

**Binary Search algorithm**#### Iterative Solution:

```
public boolean binarySearchIterative(int[] searchSpace, int target) {
int left = 0;
int right = searchSpace.length - 1;
while (left <= right) { // it is very important to put <= and not just <
// otherwise your program will give wrong answer if the target
// happens to be the last element in the search space
// Take example of searchSpace = [1, 2, 3] and target = 3
// and see what would happen.
// right would be initialized as index 2 and left as 0 giving mid = 1
// searchSpace[1] = 2 which is < target value 3
// so right remains same but left becomes mid + 1 = 1 + 1 = 2
// now, mid = left + (right - left) / 2 = 2 + (2 - 2) / 2 = 2
// searchSpace[2] = 3 = target value. Returns true.
// So here the search would terminate when left = 2 and right = 2.
int mid = left + (right - left) / 2;
if (searchSpace[mid] == target) {
return true;
} else if (searchSpace[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
```

#### Recursive Solution:

```
public boolean binarySearchRecursive(int[] searchSpace, int target) {
Arrays.sort(searchSpace); // do this only if it is not guaranteed that searchSpace is already sorted
return binarySearchRecursiveHelper(searchSpace, target, 0, searchSpace.length - 1);
}
private boolean binarySearchRecursiveHelper(int[] searchSpace, int target, int left, int right) {
if (left > right) {
return false;
}
int mid = left + (right - left) / 2;
if (searchSpace[mid] == target) {
return true;
} else if (searchSpace[mid] < target) {
return binarySearchRecursiveHelper(searchSpace, target, mid + 1, right);
} else {
return binarySearchRecursiveHelper(searchSpace, target, left, mid - 1);
}
}
```

#### Time Complexity:

Let's say we have a search space of

**elements. In a single comparison, we have cut our search space to**

*n***. Then with one more comparison we have cut it down to**

*n / 2***, and then in half and and half and half again and it goes on till the size of the search space becomes 1.**

*n / 4*Step #1 n elements | | v Step #2 (n / 2) elements | | v Step #3 (n / 4) elements | | v Step #???? 1 element

**The last element would be the element we are looking for.**So how many steps does it take to reach 1 from n by dividing by 2 at each step ? If you are familiar with

*logarithm*you would know that the answer is

**log**.

_{2}nIf we can reach 1 from n by dividing by 2 in every step in a total of

**k**steps, then that would mean if we would represent this as a tree then 2 would be the

*. Therefore, we would have*

**branching factor**

*2*^{k}= n=> log

_{2}(2

^{k}) = log

_{2}n

=> k = log

_{2}n

From the above discussion it is clear that the time complexity is O(log

_{2}n), where n = total number of elements in the search space.

### Problem Solving Using Binary Search Algorithm:

#### Problem#1: Search in Rotated Sorted Array with No Duplicates

Given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You should search for target in nums and if you found return its index, otherwise return -1.

All values of nums are unique.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

Example 3:

Input: nums = [1], target = 0

Output: -1

#### Solution:

#### Java Code and Algorithm:

Login to Access Content

#### Python Code and Algorithm:

Login to Access Content

#### Problem#2: Find Minimum in Rotated Sorted Array with Duplicates

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]

Output: 1

Example 2:

Input: [2,2,2,0,1]

Output: 0

### Java Solution and Algorithm:

Login to Access Content

#### Python Solution and Algorithm:

Login to Access Content