लिनियर सर्च और बाइनरी सर्च

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

सर्चिंग एल्गोरिदम

  • सर्चिंग एक आवश्यक ऑपरेशन है
    • करने के कई तरीके
  • कलेक्शन में किसी एलिमेंट को खोजने वाले एल्गोरिदम:
    • लिनियर सर्च
    • बाइनरी सर्च
Python में Data Structures और Algorithms

लिनियर सर्च

  • हर एलिमेंट पर लूप चलाना

बेतरतीब संख्याओं की लिस्ट का आरेखात्मक चित्रण.

  • एलिमेंट मिला
    • एल्गोरिदम रुकता है
    • रिजल्ट रिटर्न करता है
  • एलिमेंट नहीं मिला
    • एल्गोरिदम जारी रहता है
Python में Data Structures और Algorithms

लिनियर सर्च

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False
Python में Data Structures और Algorithms

लिनियर सर्च - जटिलता

  • जटिलता: $O(n)$
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण.

  • 15 ???
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. एक वैरिएबल first है जो लिस्ट की पहली पोजीशन को प्वाइंट करता है.

  • 15 ???
def binary_search(ordered_list, search_value):
  first = 0
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. एक वैरिएबल first पहली पोजीशन पर और दूसरा last आखिरी पोजीशन पर प्वाइंट करता है.

  • 15 ???
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. एक वैरिएबल first पहली पोजीशन पर, दूसरा last आखिरी पोजीशन पर, और तीसरा middle बीच की पोजीशन पर प्वाइंट करता है.

  • 15 ???
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. एक वैरिएबल first पहली पोजीशन पर, दूसरा last आखिरी पोजीशन पर, और तीसरा middle बीच की पोजीशन पर प्वाइंट करता है. बीच में 12 है और पीले रंग में दिखाया गया है.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. एक वैरिएबल first पहली पोजीशन पर प्वाइंट करता है, दूसरा last middle माइनस एक पर, और तीसरा middle बीच की पोजीशन पर. first और middle के बीच के एलिमेंट्स हरे रंग में हैं.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. एक वैरिएबल first पहली पोजीशन पर, दूसरा last आखिरी पोजीशन पर, और तीसरा middle बीच की पोजीशन पर प्वाइंट करता है. बीच में 12 है और पीले रंग में दिखाया गया है.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. first middle प्लस एक पर प्वाइंट करता है, last आखिरी पोजीशन पर, और middle बीच की पोजीशन पर. first और middle के बीच के एलिमेंट्स हरे रंग में हैं.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. middle प्वाइंटर खिसककर first और last के बीच वाले एलिमेंट पर है. first और middle के बीच के एलिमेंट्स हरे रंग में हैं.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. middle प्वाइंटर खिसककर first और last के बीच वाले एलिमेंट पर है. first और middle के बीच के एलिमेंट्स हरे रंग में हैं. middle जिस एलिमेंट, 17, पर है, उसकी 15 से तुलना होगी.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. last प्वाइंटर खिसककर first वाले नंबर पर आ गया है.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. middle प्वाइंटर खिसककर first और last के समान नंबर पर है.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. first, last, और middle तीनों 15 पर प्वाइंट कर रहे हैं, जिसकी 15 से तुलना होगी.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1
Python में Data Structures और Algorithms

बाइनरी सर्च

  • केवल ordered लिस्ट पर लागू

ordered संख्याओं वाली लिस्ट का आरेखात्मक चित्रण. नंबर 15 को घेरा गया है.

  • 15 ???
  • search_value को लिस्ट के middle आइटम से compare करें
def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False
Python में Data Structures और Algorithms

बाइनरी सर्च - जटिलता

  • जटिलता: $O(\log{}n)$

लिनियर सर्च और बाइनरी सर्च का ग्राफिकल चित्रण.

Python में Data Structures और Algorithms

अभ्यास करते हैं!

Python में Data Structures और Algorithms

Preparing Video For Download...