1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> आरओबी BOWDEN: हाय, मैं रोब हूँ.

3
00:00:15,010 --> 00:00:16,790
हम कैसे एक द्विआधारी खोज को काम करते हो?

4
00:00:16,790 --> 00:00:18,770
चलो पता करते हैं.

5
00:00:18,770 --> 00:00:23,400
तो, इस खोज से हम जा रहे हैं कि ध्यान दें
बारी बारी से लागू करने के लिए.

6
00:00:23,400 --> 00:00:27,470
तुम भी द्विआधारी खोज लागू कर सकता है
iteratively, तो आप किया है कि अगर,

7
00:00:27,470 --> 00:00:29,280
कि पूरी तरह से ठीक है.

8
00:00:29,280 --> 00:00:32,820
>> अब सबसे पहले, याद करते हैं क्या
खोज करने के लिए पैरामीटर के लिए होती हैं.

9
00:00:32,820 --> 00:00:36,120
यहाँ, हम है जो इंट मूल्य देखते हैं,
उपयोगकर्ता के मूल्य होना चाहिए

10
00:00:36,120 --> 00:00:37,320
के लिए खोज.

11
00:00:37,320 --> 00:00:40,800
हम int मूल्यों सरणी, जो देखने
हम कर रहे हैं, जिसमें सरणी है

12
00:00:40,800 --> 00:00:42,520
मूल्य के लिए खोज.

13
00:00:42,520 --> 00:00:45,602
और हम है, जो int n देखना
हमारे सरणी की लंबाई.

14
00:00:45,602 --> 00:00:47,410
>> अब, पहली बात यह है कि पहले.

15
00:00:47,410 --> 00:00:51,350
हम में N, 0 के बराबर होती है, तो देखने के लिए जाँच
हम वापसी झूठी, जिस स्थिति.

16
00:00:51,350 --> 00:00:54,770
हम एक खाली है, तो वह सिर्फ कह रहा है
सरणी, मूल्य एक में स्पष्ट रूप से नहीं है

17
00:00:54,770 --> 00:00:57,860
खाली सरणी, तो हम झूठे लौट सकते हैं.

18
00:00:57,860 --> 00:01:01,250
>> अब, हम वास्तव में बाइनरी क्या करना चाहते हैं
द्विआधारी खोज की खोज भाग.

19
00:01:01,250 --> 00:01:04,780
तो, हम मध्य मिल चाहते हैं
इस सरणी का तत्व.

20
00:01:04,780 --> 00:01:09,130
यहाँ, हम मध्य विभाजित n के बराबर होती है कहना
2 से, मध्य तत्व है के बाद से

21
00:01:09,130 --> 00:01:12,240
की लंबाई होने जा रहा
हमारे सरणी 2 से विभाजित.

22
00:01:12,240 --> 00:01:15,040
अब हम यह देखने के लिए जाँच करने के लिए जा रहे हैं
मध्य तत्व हम कर रहे हैं मूल्य के बराबर होती है

23
00:01:15,040 --> 00:01:16,160
के लिए खोज.

24
00:01:16,160 --> 00:01:21,030
मानों मध्यम मूल्य के बराबर होती है यदि हां, तो हम
हमने पाया क्योंकि सच लौट सकते हैं

25
00:01:21,030 --> 00:01:22,810
हमारे सरणी में मान.

26
00:01:22,810 --> 00:01:26,380
>> लेकिन यह सच नहीं था, तो अब
हम पुनरावर्ती करने की ज़रूरत है

27
00:01:26,380 --> 00:01:27,840
द्विआधारी खोज के कदम.

28
00:01:27,840 --> 00:01:30,450
हम या तो खोज की जरूरत
सरणी की या करने के लिए छोड़ दिया

29
00:01:30,450 --> 00:01:32,320
सरणी के बीच.

30
00:01:32,320 --> 00:01:39,280
बीच में मूल्यों है अगर तो यहाँ, हम कहते हैं
मूल्य की तुलना में कम है, जो कि मूल्य का मतलब

31
00:01:39,280 --> 00:01:41,350
मध्यम से अधिक था
सरणी की.

32
00:01:41,350 --> 00:01:45,790
इसलिए मूल्य का सही करने के लिए होना चाहिए
हम बस पर देखा कि तत्व.

33
00:01:45,790 --> 00:01:48,090
>> तो यहाँ, हम करने जा रहे हैं
बारी बारी से खोज.

34
00:01:48,090 --> 00:01:50,320
और हम हम गुजर रहे हैं पर देख लेंगे
एक सेकंड में यह करने के लिए.

35
00:01:50,320 --> 00:01:53,440
लेकिन हम करने के लिए खोज करने के लिए जा रहे हैं
मध्य तत्व की सही.

36
00:01:53,440 --> 00:01:57,710
और दूसरे मामले में, इसका मतलब है कि
मूल्य के बीच से भी कम था

37
00:01:57,710 --> 00:02:00,660
सरणी, और इसलिए हम जा रहे हैं
बाईं ओर खोज करने के लिए.

38
00:02:00,660 --> 00:02:03,520
अब बाईं होने जा रहा है
थोड़ा आसान को देखने के लिए.

39
00:02:03,520 --> 00:02:07,770
तो, हम हम बारी बारी से कर रहे हैं कि यहाँ देख
जहां पहले खोज बुला

40
00:02:07,770 --> 00:02:10,120
तर्क, फिर, मान है
हम पर देख रहे हैं.

41
00:02:10,120 --> 00:02:14,970
दूसरा तर्क होने जा रहा है
हम पर खोज कर रहे थे कि सरणी.

42
00:02:14,970 --> 00:02:17,090
और पिछले तत्व अब मध्य है.

43
00:02:17,090 --> 00:02:21,650
पिछले पैरामीटर हमारे int है याद रखें
एन, कि हमारे सरणी की लंबाई है तो.

44
00:02:21,650 --> 00:02:25,310
>> खोज करने के लिए पुनरावर्ती कॉल में, हम कर रहे हैं
अब कह रही है कि की लंबाई

45
00:02:25,310 --> 00:02:27,230
सरणी बीच है.

46
00:02:27,230 --> 00:02:32,900
तो, हमारी सरणी का आकार 20 और हम में से था अगर
मध्य के बाद से, सूचकांक 10 में खोजा

47
00:02:32,900 --> 00:02:36,930
20 2 से विभाजित है, कि हम कर रहे हैं इसका मतलब
नए रूप में 10 गुजर

48
00:02:36,930 --> 00:02:38,300
हमारे सरणी की लंबाई.

49
00:02:38,300 --> 00:02:41,910
याद रखें कि आप एक सरणी है जब
लंबाई 10 की, कि मान्य का मतलब

50
00:02:41,910 --> 00:02:45,450
तत्वों 0 से 9 तक सूचकांकों में हैं.

51
00:02:45,450 --> 00:02:50,120
तो यह हम चाहते हैं कि वास्तव में क्या है
बाईं - हमारे अद्यतन सरणी निर्दिष्ट

52
00:02:50,120 --> 00:02:53,010
मध्य तत्व से सरणी.

53
00:02:53,010 --> 00:02:55,710
>> तो, सही करने के लिए तलाश है
थोड़ा और अधिक मुश्किल.

54
00:02:55,710 --> 00:03:00,170
अब सबसे पहले, की दूरी पर विचार करते हैं
के अधिकार के लिए सरणी की

55
00:03:00,170 --> 00:03:01,240
मध्य तत्व.

56
00:03:01,240 --> 00:03:08,390
तो, हमारी सरणी आकार n का था, तो
नई सरणी आकार n ऋण का हो जाएगा

57
00:03:08,390 --> 00:03:10,140
मध्य शून्य से 1.

58
00:03:10,140 --> 00:03:12,530
तो, के एन शून्य से बीच की सोचते हैं.

59
00:03:12,530 --> 00:03:18,710
>> फिर, सरणी का आकार 20 के थे और
हम मध्य पाने के लिए 2 से विभाजित,

60
00:03:18,710 --> 00:03:23,540
इसलिए बीच फिर 10, एन शून्य से मध्यम है
हमें 10 है, इसलिए 10 देने जा रहा है

61
00:03:23,540 --> 00:03:25,330
बीच के अधिकार के लिए तत्वों.

62
00:03:25,330 --> 00:03:27,780
लेकिन हम भी इस शून्य है
1, हम नहीं करना चाहते क्योंकि

63
00:03:27,780 --> 00:03:29,700
बीच में ही शामिल हैं.

64
00:03:29,700 --> 00:03:34,190
तो एन शून्य से मध्यम शून्य से 1 हमें देता है
सही करने के लिए तत्वों की कुल संख्या

65
00:03:34,190 --> 00:03:36,800
सरणी में मध्य सूचकांक की.

66
00:03:36,800 --> 00:03:41,870
>> अब यहाँ, याद है कि मध्यम
पैरामीटर मान सरणी है.

67
00:03:41,870 --> 00:03:46,180
यहाँ तो, हम एक गुजर रहे हैं
अद्यतन मूल्यों सरणी.

68
00:03:46,180 --> 00:03:50,930
यह मूल्यों के साथ साथ मध्य प्लस 1 है
वास्तव में बारी बारी से कह फोन

69
00:03:50,930 --> 00:03:56,460
खोज, एक नई सरणी में गुजर रहा है, जहां
कि नई सरणी मध्य में शुरू होता है

70
00:03:56,460 --> 00:03:59,370
प्लस हमारे मूल मान सरणी में से एक.

71
00:03:59,370 --> 00:04:05,400
>> उस के लिए एक वैकल्पिक वाक्यविन्यास, अब है कि
आप है, संकेत देखने के लिए शुरू कर दिया है

72
00:04:05,400 --> 00:04:10,170
एम्परसेंड मूल्यों मध्य प्लस 1.

73
00:04:10,170 --> 00:04:17,149
इसलिए, बीच का पता हड़पने
मूल्यों के साथ साथ एक तत्व.

74
00:04:17,149 --> 00:04:23,690
>> अब, आप सहज नहीं थे
आप की तरह है कि एक सरणी संशोधित

75
00:04:23,690 --> 00:04:28,900
भी उपयोग कर यह लागू हो सकता था
एक पुनरावर्ती सहायक समारोह, जहां

76
00:04:28,900 --> 00:04:31,680
कि सहायक समारोह लेता है
अधिक तर्क.

77
00:04:31,680 --> 00:04:36,610
तो बजाय सिर्फ मान लेने की,
सरणी, और सरणी के आकार,

78
00:04:36,610 --> 00:04:42,315
सहायक समारोह में अधिक समय लग सकता है
कम सूचकांक सहित तर्कों,

79
00:04:42,315 --> 00:04:45,280
आप सरणी में के बारे में परवाह है कि
और कि तुम ध्यान से ऊपरी सूचकांक

80
00:04:45,280 --> 00:04:46,300
सरणी के बारे में.

81
00:04:46,300 --> 00:04:49,770
>> और इसलिए दोनों कम का ट्रैक रखने
सूचकांक और ऊपरी सूचकांक, तुम नहीं करते

82
00:04:49,770 --> 00:04:52,780
कभी संशोधित करने की आवश्यकता
मूल मान सरणी.

83
00:04:52,780 --> 00:04:56,390
तुम बस के लिए जारी रख सकते हैं
मानों सरणी का उपयोग करें.

84
00:04:56,390 --> 00:04:59,540
लेकिन यहां हम एक सहायक की जरूरत नहीं है नोटिस
जब तक हम कर रहे हैं के रूप में कार्य

85
00:04:59,540 --> 00:05:01,760
मूल को संशोधित करने के लिए तैयार
मानों सरणी.

86
00:05:01,760 --> 00:05:05,020
हम में पारित करने के लिए तैयार हैं
एक अद्यतन मूल्यों.

87
00:05:05,020 --> 00:05:09,140
>> अब, हम पर द्विआधारी खोज नहीं कर सकते
unsorted है कि एक सरणी.

88
00:05:09,140 --> 00:05:12,220
तो, चलो इस हल करते हैं.

89
00:05:12,220 --> 00:05:17,650
अब, कि तरह अतीत है नोटिस दो
पैरामीटर है, जो मूल्यों int

90
00:05:17,650 --> 00:05:21,110
हम छँटाई कर रहे हैं कि सरणी, और int n,
सरणी की लंबाई है जो कि

91
00:05:21,110 --> 00:05:22,250
हम छँटाई कर रहे हैं.

92
00:05:22,250 --> 00:05:24,840
तो, यहाँ हम लागू करना चाहते हैं
एक छँटाई कलन विधि

93
00:05:24,840 --> 00:05:26,690
n के ओ चुकता है.

94
00:05:26,690 --> 00:05:30,560
आप बुलबुला तरह, चयन चुन सकते हैं
क्रमबद्ध करें, या सम्मिलन सॉर्ट, या

95
00:05:30,560 --> 00:05:32,670
हम नहीं है कुछ अन्य प्रकार
क्लास में देखा.

96
00:05:32,670 --> 00:05:36,380
लेकिन यहाँ, हम करने जा रहे हैं
चयन प्रकार का उपयोग.

97
00:05:36,380 --> 00:05:40,030
>> तो, हम पुनरावृति करने के लिए जा रहे हैं
पूरे सरणी से अधिक.

98
00:05:40,030 --> 00:05:44,360
खैर, हम यहाँ हम पुनरावृति रहे हैं कि देखने
0 से n करने के लिए शून्य से 1.

99
00:05:44,360 --> 00:05:45,990
क्यों नहीं सभी तरह से पता करने के लिए ऊपर?

100
00:05:45,990 --> 00:05:49,320
खैर, हम पहले से ही हल है कि अगर पहले
फिर n शून्य से 1 तत्वों,

101
00:05:49,320 --> 00:05:54,420
पहले से ही होना चाहिए क्या बहुत पिछले तत्व
सही जगह में, तो खत्म छँटाई

102
00:05:54,420 --> 00:05:56,520
पूरे सरणी.

103
00:05:56,520 --> 00:05:58,770
>> अब, याद कैसे चयन
सॉर्ट काम करता है.

104
00:05:58,770 --> 00:06:01,950
हम पूरे सरणी पर जाने के लिए जा रहे हैं
में न्यूनतम मूल्य की तलाश

105
00:06:01,950 --> 00:06:04,480
सरणी और छड़ी कि
शुरुआत में.

106
00:06:04,480 --> 00:06:07,610
तो फिर हम पूरे पर जाने के लिए जा रहे हैं
सरणी फिर दूसरे की तलाश में

107
00:06:07,610 --> 00:06:10,410
छोटी तत्व, और छड़ी कि
में दूसरे स्थान पर

108
00:06:10,410 --> 00:06:12,100
सरणी, और इतने पर.

109
00:06:12,100 --> 00:06:14,330
तो, कि यह क्या कर रहा है है.

110
00:06:14,330 --> 00:06:17,290
>> यहाँ, हम हम कर रहे हैं कि देख रहे हैं
वर्तमान न्यूनतम सेटिंग

111
00:06:17,290 --> 00:06:20,030
मैं वें सूचकांक के लिए मूल्य.

112
00:06:20,030 --> 00:06:23,160
इसलिए पहली यात्रा पर, हम जा रहे हैं
न्यूनतम मूल्य होने पर विचार करने के लिए

113
00:06:23,160 --> 00:06:25,030
हमारे सरणी की शुरुआत.

114
00:06:25,030 --> 00:06:28,500
फिर, हम पर पुनरावृति करने जा रहे हैं
करने के लिए जाँच सरणी, का शेष

115
00:06:28,500 --> 00:06:31,870
वहाँ की तुलना में किसी भी तत्व के रूप में बड़ा अगर देखना
हम वर्तमान में कर रहे हैं कि एक

116
00:06:31,870 --> 00:06:33,900
न्यूनतम पर विचार.

117
00:06:33,900 --> 00:06:38,840
>> तो यहाँ, जम्मू प्लस एक मान - कि है
वर्तमान में हम क्या कर रहे हैं से भी कम

118
00:06:38,840 --> 00:06:40,380
न्यूनतम पर विचार.

119
00:06:40,380 --> 00:06:42,940
तो फिर हम अद्यतन करने के लिए जा रहे हैं
हम कम से कम करने के लिए है

120
00:06:42,940 --> 00:06:44,640
सूचकांक जम्मू प्लस 1.

121
00:06:44,640 --> 00:06:48,540
तो, पूरे सरणी पार करना है कि,
और इस के बाद पाश, न्यूनतम के लिए

122
00:06:48,540 --> 00:06:53,160
से न्यूनतम तत्व होना चाहिए
सरणी में मैं वें स्थिति.

123
00:06:53,160 --> 00:06:57,350
>> हम चाहते हैं कि एक बार जब हमें स्वैप कर सकते हैं
मैं वें स्थिति में न्यूनतम मूल्य

124
00:06:57,350 --> 00:06:58,230
सरणी में.

125
00:06:58,230 --> 00:07:00,130
तो यह सिर्फ एक मानक स्वैप है.

126
00:07:00,130 --> 00:07:03,940
हम एक अस्थायी मूल्य में दुकान -
सरणी में मैं वें मूल्य -

127
00:07:03,940 --> 00:07:08,460
सरणी में मैं वें मूल्य में डाल
वहाँ है कि न्यूनतम मूल्य,

128
00:07:08,460 --> 00:07:13,580
और फिर जहां में वापस की दुकान
हुआ करते थे मौजूदा न्यूनतम मूल्य

129
00:07:13,580 --> 00:07:16,460
सरणी में मैं वें मूल्य, तो
हम इसे खोना नहीं था कि.

130
00:07:16,460 --> 00:07:20,510
>> तो, उस पर जारी है
अगली यात्रा.

131
00:07:20,510 --> 00:07:23,480
हम दूसरे की तलाश शुरू कर देंगे
न्यूनतम मूल्य और उस में डालने

132
00:07:23,480 --> 00:07:24,590
दूसरे स्थान पर.

133
00:07:24,590 --> 00:07:27,440
तीसरी यात्रा पर, हम देख लेंगे
तीसरा न्यूनतम मूल्य और सम्मिलित

134
00:07:27,440 --> 00:07:31,550
कि तीसरी स्थिति में है, और इसलिए
हम एक हल सरणी है जब तक पर.

135
00:07:31,550 --> 00:07:33,820
मेरा नाम रोब है, और इस
चयन के आधार पर क्रमबद्ध किया गया था.

136
00:07:33,820 --> 00:07:39,456