1
00:00:00,700 --> 00:00:01,660
Hi everyone.

2
00:00:01,660 --> 00:00:06,280
This question is about a very important concept called the binary search.

3
00:00:06,280 --> 00:00:11,560
Now this is a very helpful method to search in data which is sorted now.

4
00:00:11,560 --> 00:00:16,660
It can be numbers which are sorted either ascending or descending, or it can be characters or strings

5
00:00:16,660 --> 00:00:18,970
which are sorted alphabetically, etc..

6
00:00:18,970 --> 00:00:24,850
Now whenever you are doing any question where data which is given to you is sorted, think whether you

7
00:00:24,850 --> 00:00:26,800
can solve it using binary search.

8
00:00:26,800 --> 00:00:31,600
Now let's go ahead and read the question and let's try to understand how binary search works.

9
00:00:31,600 --> 00:00:37,900
Given an array of integers, which is sorted in ascending order and a target integer, write a function

10
00:00:37,900 --> 00:00:41,530
to search for whether the target integer is there in the given array.

11
00:00:41,530 --> 00:00:45,670
If it is there, then return its index, otherwise return minus one.

12
00:00:45,670 --> 00:00:50,110
You must write an algorithm with O of log n runtime complexity.

13
00:00:50,110 --> 00:00:51,670
Now this is the catch over here right?

14
00:00:51,670 --> 00:00:54,490
So let's say this is the array which is given to you over here.

15
00:00:54,490 --> 00:00:58,360
And let's say the target value which you're searching for is 11.

16
00:00:58,360 --> 00:01:02,920
Now you could do a simple search where you try to just go through the array.

17
00:01:02,920 --> 00:01:03,100
Right.

18
00:01:03,100 --> 00:01:04,360
You're iterating through the array.

19
00:01:04,360 --> 00:01:06,550
You check whether this value is 11.

20
00:01:06,550 --> 00:01:07,330
No it's not.

21
00:01:07,330 --> 00:01:08,020
So you proceed.

22
00:01:08,020 --> 00:01:09,940
You check whether this value over here is 11.

23
00:01:09,940 --> 00:01:11,080
It's not equal to 11.

24
00:01:11,080 --> 00:01:12,220
So you proceed, etc..

25
00:01:12,220 --> 00:01:12,490
Right.

26
00:01:12,490 --> 00:01:17,770
But in that case the time complexity is going to be o of n, where n is the number of elements in the

27
00:01:17,770 --> 00:01:18,100
array.

28
00:01:18,100 --> 00:01:23,740
But over here it's mentioned that the solution has to have a time complexity of O of log n.

29
00:01:23,740 --> 00:01:26,860
So this is where the binary search comes into picture.

30
00:01:26,860 --> 00:01:32,350
And remember o of log n is much, much better than O of n or linear time complexity.

31
00:01:32,350 --> 00:01:37,210
And we have already discussed that in previous videos where we discussed the time complexity, right?

32
00:01:37,210 --> 00:01:40,150
For example, if n is equal to, let's say four, right?

33
00:01:40,150 --> 00:01:45,940
So if n is equal to four, o of n will be four o of log, n will be equal to only two.

34
00:01:46,060 --> 00:01:48,460
Because we know log of four is equal to two.

35
00:01:48,460 --> 00:01:48,640
Right.

36
00:01:48,640 --> 00:01:50,110
Because what is log n.

37
00:01:50,110 --> 00:01:52,210
It's actually the power of two.

38
00:01:52,240 --> 00:01:55,030
You have to raise it to so that you get this four over here.

39
00:01:55,030 --> 00:01:57,010
Now two to the power two is equal to four.

40
00:01:57,010 --> 00:01:58,870
So that's why log four is equal to two.

41
00:01:58,870 --> 00:02:03,220
Now similarly if n is equal to let's say two to the power 100 right.

42
00:02:03,220 --> 00:02:07,180
So this value over is value over here is going to be a very big value.

43
00:02:07,180 --> 00:02:13,210
But when we do O of log two to the power 100 this is only going to be equal to 100.

44
00:02:13,210 --> 00:02:16,540
Now you can see that there is a huge difference between these two right.

45
00:02:16,540 --> 00:02:19,660
So that's why the binary search is a very useful algorithm.

46
00:02:19,660 --> 00:02:25,540
So let's proceed and go ahead and develop some intuition about how the binary search works.

47
00:02:25,540 --> 00:02:29,770
Now remember this works only when the data which is given to you is sorted.

48
00:02:29,770 --> 00:02:32,290
Now let's take an example in daily life.

49
00:02:32,290 --> 00:02:37,570
So over here you have your teacher, and the teacher has answer sheets in her hand.

50
00:02:37,570 --> 00:02:44,080
So there was a recent exam and she has evaluated it and she has sorted the answer sheets as per the

51
00:02:44,080 --> 00:02:45,520
roll number of the class.

52
00:02:45,520 --> 00:02:46,060
All right.

53
00:02:46,090 --> 00:02:50,620
Now let's say she has sorted the answer sheets over here in ascending order.

54
00:02:50,620 --> 00:02:53,050
So these are the roll numbers 1 to 10.

55
00:02:53,050 --> 00:02:57,100
Now let's say you want to find the answer sheet of roll number seven.

56
00:02:57,100 --> 00:02:58,600
Let's say your roll number is seven.

57
00:02:58,600 --> 00:03:02,380
And you want to find this answer sheet from this pile of answer sheets.

58
00:03:02,380 --> 00:03:06,130
Right now one way you could do is you could go through one by one.

59
00:03:06,130 --> 00:03:11,020
But another way, typically how you would have done it in class is, let's say you opened it up to this

60
00:03:11,020 --> 00:03:13,690
part over here and you can see that it's six, right.

61
00:03:13,690 --> 00:03:15,730
So you are opening it to the middle.

62
00:03:15,730 --> 00:03:17,140
You see it's over here.

63
00:03:17,140 --> 00:03:18,130
The roll number is six.

64
00:03:18,130 --> 00:03:24,370
So you can be sure that the answer sheet with roll number seven is not going to be in any of these parts.

65
00:03:24,370 --> 00:03:24,580
Right.

66
00:03:24,580 --> 00:03:30,160
So you can just directly eliminate the whole of this part without even looking at each of these individually.

67
00:03:30,160 --> 00:03:33,400
So that's how the binary search works right now.

68
00:03:33,400 --> 00:03:35,410
Again remember the opposite of it.

69
00:03:35,410 --> 00:03:37,720
Or the alternative is the linear search.

70
00:03:38,260 --> 00:03:43,480
Now in the case of linear search, as we discussed, you would be just checking one by one till you

71
00:03:43,480 --> 00:03:44,590
reach the roll.

72
00:03:44,590 --> 00:03:45,280
Number seven.

73
00:03:45,280 --> 00:03:51,550
Now this over here, this operation over here, which is a linear search, is an O of n time complexity

74
00:03:51,550 --> 00:03:52,060
operation.

75
00:03:52,060 --> 00:03:57,490
So and then we have seen that in this question we need a time complexity of o of log n.

76
00:03:57,490 --> 00:03:57,850
All right.

77
00:03:57,880 --> 00:04:03,220
Now one more interesting thing which we can observe over here is inbuilt functions in JavaScript such

78
00:04:03,220 --> 00:04:06,100
as index of etc. operate in this manner.

79
00:04:06,100 --> 00:04:10,840
They are just going to search one by one, and the time complexity of these type of operations, like

80
00:04:10,840 --> 00:04:13,300
index off is going to be O of n.

81
00:04:13,300 --> 00:04:17,320
Now for example, if this was the array and let's say this array was numb's.

82
00:04:17,320 --> 00:04:20,920
So then you could have just done numb's dot index off.

83
00:04:20,920 --> 00:04:22,990
And let's say you are searching for seven.

84
00:04:22,990 --> 00:04:25,210
You could say Numb's dot index of seven.

85
00:04:25,210 --> 00:04:25,510
Right.

86
00:04:25,510 --> 00:04:29,920
So that would give you back this index 012345 and six.

87
00:04:29,920 --> 00:04:31,090
So this is index six.

88
00:04:31,090 --> 00:04:33,550
So it will give you back the index which is six.

89
00:04:33,820 --> 00:04:39,340
Built in functions in JavaScript such as index off actually under the hood are doing a linear search

90
00:04:39,340 --> 00:04:41,320
which is an O of n operation.

91
00:04:41,320 --> 00:04:41,800
All right.

92
00:04:41,830 --> 00:04:46,600
Now let's go ahead and think about a little bit about what are the interesting things that we can note

93
00:04:46,600 --> 00:04:48,550
about the binary search algorithm.

94
00:04:48,550 --> 00:04:54,040
This is going to be a divide and conquer algorithm, where we are going to divide the array which is

95
00:04:54,040 --> 00:04:56,050
given to us into two parts at every step.

96
00:04:56,050 --> 00:04:58,720
And we are going to eliminate half of it at every step.

97
00:04:58,720 --> 00:05:00,250
So that's how the binary search.

98
00:05:00,410 --> 00:05:01,130
Got them works.

99
00:05:01,130 --> 00:05:03,080
And remember this will work.

100
00:05:03,080 --> 00:05:08,570
The caveat is you can apply the binary search only if the data which is given to you is sorted.

101
00:05:08,570 --> 00:05:09,740
So this is very important.

102
00:05:09,740 --> 00:05:15,350
If it's integers, it can be ascending or descending, or if the data is strings it can be alphabetical,

103
00:05:15,350 --> 00:05:15,980
etc..

104
00:05:15,980 --> 00:05:19,340
In the next video let's try to understand the method and the.

105
00:05:19,370 --> 00:05:23,390
And then let's go ahead and do the complexity analysis of the binary search algorithm.