[సంగీతాన్ని] 

డౌ LLOYD: అన్ని కుడి. కాబట్టి బైనరీ శోధన ఉంది మేము ఉపయోగించే అల్గారిథమ్ ఒక శ్రేణి యొక్క లోపల ఒక మూలకం కనుగొనేందుకు. సరళ శోధన లాగ కాకుండా ఇది అవసరము ప్రత్యేక పరిస్థితి, ముందుగానే కలుసుకున్నారు కానీ అది చాలా సమర్థవంతంగా ఉంటే వార్తలు పరిస్థితి అని, నిజానికి, కలుసుకున్నారు. 

సో ఆలోచన ఏమిటి? అది విభజించి జయించటానికి ఉంది. మేము యొక్క పరిమాణం తగ్గించడానికి కావలసిన సగం ప్రతిసారీ ద్వారా శోధన ప్రాంతం ఒక లక్ష్యం సంఖ్య కనుగొనేందుకు చేయడానికి. ఈ పేరు ఆ పరిస్థితి ఉంది అయితే, తెరపైకి వస్తుంది. మేము మాత్రమే శక్తి సామర్థ్యాలు పరపతి చేయవచ్చు అంశాల తొలగించడం సగం కూడా చూడటం లేకుండా వాటిని శ్రేణి క్రమబద్ధీకరించబడింది ఉంటే. 

అది ఒక పూర్తి అప్ మిశ్రమాన్ని ఉంటే, మేము కేవలం చేతి బయటకు కాదు ఎందుకంటే, మూలకాల యొక్క సగం తొలగించాలనుకుంటున్నారా మేము తొలగించటం ఏమి తెలియదు. కానీ శ్రేణి, క్రమబద్ధీకరించబడింది ఉంటే మేము ఆ చేయవచ్చు మేము ఎందుకంటే ఆ ప్రతిదీ తెలిసి మేము ప్రస్తుతం ఇక్కడ వదిలి కంటే తక్కువ ఉండాలి విలువ మేము ప్రస్తుతం ఉన్నారు. మరియు ప్రతిదీ మేము ఎక్కడ కుడి విలువ కంటే ఎక్కువ ఉండాలి మేము ప్రస్తుతం శోధిస్తున్న. 

సో pseudocode ఏమిటి బైనరీ శోధన కోసం చర్యలు? మేము వరకు ఈ ప్రక్రియ పునరావృతం శ్రేణి లేదా, మేము ద్వారా కొనసాగండి, ఉప శ్రేణులను చిన్న తునకలుగా అసలు శ్రేణి, పరిమాణం 0 యొక్క ఉంది. Midpoint లెక్కించు ప్రస్తుత ఉప శ్రేణి యొక్క. 

మీరు చూస్తున్న విలువ ఉంటే యెరే యొక్క మూలకం, ఆపడానికి. మీరు కనుగొన్నారు. ఆ గొప్ప పని. లేకపోతే, లక్ష్యం ఉంటే మధ్యలో వద్ద ఏది కంటే తక్కువ, కాబట్టి విలువ ఉంటే మేము చూస్తున్నారా , మేము చూసే కంటే తక్కువగా ఉంటుంది మళ్లీ ఈ ప్రక్రియ పునరావృతం, కానీ బదులుగా, ముగింపు బిందువు మార్చడానికి అసలు అనే పూర్తి శ్రేణి పూర్తి కేవలం ఎడమ ఉండాలి ఇక్కడ మేము కేవలం చూసారు. 

మేము మధ్య చాలా ఎక్కువగా ఉందని తెలుసు లేదా లక్ష్యం, మధ్య కంటే తక్కువ మరియు కనుక ఇది ఉనికిలో ఉండాలి ఉంటే అన్ని వద్ద శ్రేణి లో ఉంది ఎక్కడో midpoint యొక్క ఎడమ. కాబట్టి మేము శ్రేణి సెట్ చేస్తాము కేవలం ఎడమ నగర కొత్త ముగింపు బిందువుగా midpoint యొక్క. దీనికి విరుద్ధంగా, లక్ష్యం ఉంటే మధ్యలో వద్ద ఏది కంటే ఎక్కువ, మేము ఖచ్చితమైన చేయండి ప్రక్రియ, కానీ బదులుగా మేము అని ప్రారంభ బిందువుగా మార్చడానికి కేవలం midpoint కుడివైపున మేము కేవలం లెక్కించిన. ఆపై, మేము మళ్లీ ప్రక్రియ ప్రారంభం. 

యొక్క OK, ఈ ఊహించడానికి లెట్? కాబట్టి వెళ్లి ఇక్కడ ఒక చాలా ఉంది, కానీ ఇక్కడ 15 మూలకాల యొక్క ఒక శ్రేణి. మరియు మేము పర్యవేక్షించడం కావడం చాలా అంశాలు ఈ సమయం. సో సరళ శోధన, మేము కేవలం ఒక లక్ష్యం గురించి caring. కానీ ఈ సమయంలో మేము కావలసిన మేము ఎక్కడ పట్టించుకోనట్లు చూడండి మొదలు ఎక్కడ మేము చూస్తున్న నిలుపుదల ఉంటాయి, మరియు midpoint ఏమిటి ప్రస్తుత శ్రేణి యొక్క. కాబట్టి ఇక్కడ మేము బైనరీ శోధన వెళ్ళండి. మేము చాలా చక్కని మంచి వెళ్ళడానికి, కుడి ఉన్నాము? నేను అణిచివేసేందుకు వెళుతున్న సూచీలు సమితి ఇక్కడ క్రింద. ఈ ప్రాథమికంగా కేవలం ఏ అంశం యెరే యొక్క మేము గురించి మాట్లాడటం చేస్తున్నాం. సరళ శోధన తో, మేము మేము అంతవరకు వంటి, శ్రద్ధ ఎన్ని తెలుసుకోవాలి మేము పైగా iterating చేస్తున్న అంశాలు, కానీ మేము నిజంగా శ్రద్ధ లేదు ఏమి మూలకం మేము ప్రస్తుతం శోధిస్తున్న. బైనరీ శోధన, మేము. కాబట్టి ఆ కేవలం అక్కడ ఒక చిన్న మార్గదర్శకంగా. 

కాబట్టి మేము కుడి, ప్రారంభించవచ్చు? బాగా, కాదు చాలా. నేను అన్నాడు ఏమి గుర్తుంచుకో బైనరీ శోధన గురించి? మేము ఒక ఆన్ చెయ్యలేరని వేరే క్రమబద్ధీకరించనిది శ్రేణి లేదా, మేము ఆ హామీ లేదు కొన్ని అంశాలు లేదా విలువలను కాదు అనుకోకుండా ఉండటం విస్మరించిన మనం కేవలం యెరే యొక్క సగం విస్మరించండి నిర్ణయించుకుంటారు. 

కాబట్టి బైనరీ శోధన వన్ స్టెప్ మీరు ఒక క్రమబద్ధీకరించబడతాయి శ్రేణి కలిగి ఉండాలి ఉంది. మరియు మీరు విభజన ఏ ఉపయోగించవచ్చు మేము గురించి మాట్లాడారు చేసిన అల్గోరిథంలు ఆ స్థానానికి మీరు పొందుటకు. కాబట్టి ఇప్పుడు, మేము ఒక స్థానం ఎక్కడ ఉన్నారు మేము బైనరీ శోధన పని చేయవచ్చు. 

కాబట్టి యొక్క విధానాన్ని పునరుక్తి తెలియజేయండి అంచెలంచెలుగా మరియు ఉంచడానికి మేము వెళ్ళి ఏం ట్రాక్. కాబట్టి మొదటి మేము లెక్కించేందుకు చేయవలసిందల్లా ప్రస్తుత శ్రేణి యొక్క midpoint. Well, మేము మొదటి, మేము ఉన్నాము సే చేస్తాము అన్ని విలువ 19 వెతుకుతున్న. మేము సంఖ్య 19 కనుగొనేందుకు ప్రయత్నిస్తున్న. ఈ మొదటి మూలకం అర్రే, సూచిక సున్నా వద్ద ఉన్న మరియు ఈ చివరి మూలకం అర్రే సూచిక 14 వద్ద ఉంది. కాబట్టి మేము ఆ ప్రారంభ మరియు ముగింపు పిలుస్తాను. 

కాబట్టి మేము midpoint ద్వారా లెక్కించేందుకు 0 ప్లస్ 2 ద్వారా విభజించబడింది 14 జోడించడం; అందంగా సూటిగా midpoint. మరియు మేము చెప్పగలను midpoint ఇప్పుడు 7 ఉంది. కాబట్టి 15 మేము చూస్తున్న ఏమి ఉంది? అది కాదు. మేము 19 చూస్తున్న. కానీ మేము 19 ఎక్కువేమీ కాదని తెలుసు మేము మధ్య వద్ద దొరకలేదు ఏమి కంటే. 

కాబట్టి మేము చేయవచ్చు ఏమి ఉంది ప్రారంభ బిందువుగా మార్చడానికి కేవలం కుడి ఉండాలి midpoint, మరియు మరలా విధానాన్ని పునరుక్తి. మేము అలా చేసినప్పుడు, మేము ఇప్పుడు చెప్పండి కొత్త ప్రారంభ బిందువుగా శ్రేణి నగర 8. మనం సమర్థవంతంగా పూర్తి చేసిన ఉంది 15 ఎడమవైపున నిర్లక్ష్యం ప్రతిదీ. మేము సగం తొలగించింది చేసిన సమస్య, మరియు ఇప్పుడు, బదులుగా అన్వేషణ కలిగి మా శ్రేణి లో 15 పైగా అంశాలు, మేము మాత్రమే 7 వెతుకుతున్నాం. 8 కొత్త ప్రారంభ బిందువుగా ఉంది. 14 ఇప్పటికీ ముగింపు స్థానం. 

ఇప్పుడు, మేము మళ్ళీ ఈ పైగా వెళ్ళి. మేము కొత్త midpoint లెక్కించేందుకు. 8 ప్లస్ 14 2 11 ద్వారా విభజించబడింది, 22 ఉంది. ఈ మేము చూస్తున్న ఏమి ఉంది? అది కాదు. మేము ఒక విలువ కోసం చూస్తున్నారా మేము కేవలం దొరకలేదు ఏమి కంటే తక్కువ. కాబట్టి మేము పునరుక్తి చూడాలని మళ్లీ ప్రక్రియ. మేము ముగింపు పాయింట్ మార్చడానికి వెళుతున్న కేవలం midpoint యొక్క ఎడమవైపు ఉంటుంది. కాబట్టి కొత్త ముగింపు పాయింట్ 10 అవుతుంది. మరియు ఇప్పుడు, ఆ మాత్రమే భాగం అర్రే మనం ద్వారా క్రమం ఉంటుంది. కాబట్టి మేము ఇప్పుడు తొలగించాయి 15 అంశాల 12. మేము తెలుసు 19 ఉంటే శ్రేణి లో ఉనికిలో ఉంది, అది మూలకం మధ్య ఎక్కడో ఉన్నాయి ఉండాలి సంఖ్య 8 మరియు మూలకం సంఖ్య 10. 

కాబట్టి మేము మళ్ళీ కొత్త midpoint లెక్కించేందుకు. 8 ప్లస్ 10 2 9 ద్వారా విభజించబడింది, 18. మరియు ఈ సందర్భంలో, చూడండి లక్ష్యం మధ్య వద్ద ఉంది. మేము కోసం చూస్తున్నారా వేటి దొరకలేదు. మేము మానివేయవచ్చు. మేము విజయవంతంగా పూర్తి ఒక బైనరీ శోధన. అయితే సరే. కాబట్టి మేము ఈ అల్గోరిథం తెలుసు లక్ష్యం ఉంటే పనిచేస్తుంది ఎక్కడో శ్రేణి యొక్క లోపల. ఈ అల్గోరిథం పని ఉంటే డజ్ లక్ష్యం వ్యూహంలో కాదు? సరే, అది ప్రారంభిద్దాం మళ్ళీ, మరియు ఈ సమయంలో, యొక్క మూలకం కోసం చూద్దాం దృశ్యపరంగా మేము చూడగలిగే 16, శ్రేణి లో ఎక్కడైనా ఉనికిలో లేదు. 

ప్రారంభ బిందువుగా మళ్ళీ 0. ముగింపు బిందువు మళ్ళీ 14 ఉంది. ఆ మొదటి సూచీలు మరియు పూర్తి శ్రేణి యొక్క చివరి అంశాలు. మరియు మేము ప్రక్రియ మేము ద్వారా వెళ్తారో ద్వారా వెళ్ళింది మళ్ళీ, 16 కనుగొనేందుకు ప్రయత్నిస్తున్న, కూడా దృష్టి అయితే, మేము ఇప్పటికే చెయ్యవచ్చు అక్కడ మాత్రం కాదు చెప్పడం. మేము కేవలం ఖచ్చితంగా ఈ అల్గోరిథం చేయాలనుకుంటున్నాము నిజానికి, ఇప్పటికీ కొన్ని విధంగా పని చేస్తుంది మరియు కేవలం మాకు వదిలి లేదు ఒక అనంతమైన లూప్ లో కష్టం. 

కాబట్టి స్టెప్ మొదటి ఏమిటి? Midpoint లెక్కించు ప్రస్తుత శ్రేణి యొక్క. Midpoint ఏమిటి ప్రస్తుత శ్రేణి యొక్క? సరే, కుడి, 7 వార్తలు? 2 ద్వారా విభజించబడింది 14 ప్లస్ 0 7. మేము చూస్తున్న ఏమి 15? నం ఇది చాలా దగ్గరలో, కానీ మేము చూస్తున్న కంటే కొద్దిగా పెద్ద విలువ. 

కాబట్టి మేము అది జరగబోతోంది తెలుసు 15 ఎడమవైపున ఎక్కడా. లక్ష్యం కంటే ఎక్కువ ఏమి midpoint ఉంది. కాబట్టి మేము కొత్త ప్రారంభం సమయం వరకు సెట్ కేవలం మధ్య కుడి చేతి వైపున. Midpoint కాబట్టి, ప్రస్తుతం 7 యొక్క కొత్త ప్రారంభం పాయింట్ 8 అని పిలవబడు. మరియు మేము సమర్థవంతంగా ఏమి చేసిన మళ్ళీ పూర్తి విస్మరించబడుతుంది యెరే యొక్క మొత్తం లెఫ్ట్ హాఫ్. 

ఇప్పుడు, మేము పునరావృతం మరొకసారి ప్రాసెస్. కొత్త midpoint లెక్కించేందుకు. 8 ప్లస్ 14 2 11 ద్వారా విభజించబడింది, 22 ఉంది. మేము చూస్తున్న ఏమి 23 ఏమిటి? దురదృష్టవశాత్తు, లేదు. మేము ఒక విలువ కోసం చూస్తున్నారా కంటే తక్కువ 23 ఉంది. కాబట్టి ఈ సందర్భంలో, మనం చేయబోతున్నామని ముగింపు బిందువు మార్చడానికి కేవలం ఉండాలి ప్రస్తుత midpoint ఎడమవైపున. ప్రస్తుత midpoint 11, మరియు కాబట్టి మేము కొత్త ముగింపు పాయింట్ సెట్ చేస్తాము మేము వెళ్ళి తదుపరి సారి 10 ఈ విధానం ద్వారా. 

మళ్లీ, మేము మళ్లీ ప్రక్రియ ద్వారా వెళ్లండి. Midpoint లెక్కించేందుకు. 2 ద్వారా విభజించబడింది 8 ప్లస్ 10 9 ఉంటుంది. మేము చూస్తున్న ఏమి 19? దురదృష్టవశాత్తు, లేదు. మేము ఇంకా చూస్తున్న కంటే తక్కువ ఒక సంఖ్య. కాబట్టి మేము ముగింపు బిందువు ఈ సమయంలో మారుస్తాము కేవలం midpoint ఎడమవైపున ఉండాలి. Midpoint, ప్రస్తుతం 9 కాబట్టి ముగింపు పాయింట్ 8 ఉంటుంది. ఇప్పుడు, మేము కేవలం చూస్తున్నారా ఒకే మూలకం శ్రేణి వద్ద. 

ఈ శ్రేణి యొక్క midpoint ఏమిటి? సరే, అది, 8 వద్ద మొదలవుతుంది 8 వద్ద ముగుస్తుంది, midpoint 8. ఆ మేము చూస్తున్న ఏమి ఉంది? మేము 17 కోసం చూస్తున్నాయి? లేదు, మేము 16 చూస్తున్న. అది యెరే నందలి ఉంది కనుక, ఇది ఎక్కడో ఉన్నాయి ఉండాలి మేము ప్రస్తుతం ఎక్కడ ఎడమవైపున. కాబట్టి మేము ఏమి వెళ్తున్నారు? బాగా, మేము కేవలం అంతం పాయింట్ సెట్ చేస్తాము ప్రస్తుత midpoint ఎడమవైపున. కాబట్టి మేము 7 ముగింపు పాయింట్ మారుస్తాము. మీరు ఏమి కేవలం చూడలేదా అయితే, ఇక్కడ జరిగింది? ఇప్పుడు ఇక్కడ చూడండి. 

ఇప్పుడు ప్రారంభించు ముగింపు కంటే ఎక్కువ. ఫలితంగా, రెండు చివరల మా శ్రేణి యొక్క అధిగమించి, మరియు ప్రారంభ బిందువుగా ఉంది ఇప్పుడు ముగింపు బిందువు తర్వాత. Well, ఆ లేదు కుడి, ఏ అర్ధవంతం? కాబట్టి ఇప్పుడు, ఏమి మేము చెప్పగలను మనం పరిమాణం 0 యొక్క ఒక ఉప శ్రేణి కలిగి. మరియు ఒకసారి మేము సంపాదించిన చేస్తున్నారు ఈ సమయంలో, మేము ఇప్పుడు చెయ్యవచ్చు ఆ మూలకం హామీ 16 శ్రేణి లో ఉనికిలో లేదు, ప్రారంభ బిందువుగా ఎందుకంటే మరియు ముగింపు బిందువు దాటింది. కాబట్టి అది కాదు. ఇప్పుడు, ఈ కొద్దిగా ఉంది అని గుర్తించలేకపోతే ప్రారంభ బిందువుగా మరియు ముగింపు కంటే వివిధ అదే ఉండటం అభిప్రాయపడుతున్నారు. మేము చూస్తున్న అయివుంటే 17, అది కలిగి ఉంటుంది అర్రే, మరియు ప్రారంభ బిందువుగా వున్నాడని గత మళ్ళా మరియు ముగింపు బిందువు ఆ పాయింట్లు దాటింది ముందు, మేము అక్కడ 17 దొరకలేదు ఉండేది. వారు మేము ఆ దాటి మాత్రమే ఇది మూలకం లేదని హామీ శ్రేణి ఉన్నాయి. 

కాబట్టి యొక్క చాలా తక్కువ తీసుకుందాం సరళ శోధన కంటే దశలను. చెత్త దృష్టాంతంలో, మేము కలిగి n మూలకాల ఒక జాబితా విడిపోయినట్లు పదేపదే సగం లో, టార్గెట్ కనుగొనేందుకు గాని ఎందుకంటే లక్ష్యం మూలకం గత ఎక్కడో ఉంటుంది విభజన, లేదా అది అన్ని వద్ద ఉనికిలో లేదు. చెత్త సందర్భంలో, మేము కలిగి మీరు తెలుసు శ్రేణి విడిపోయారు? N సార్లు లాగ్; మేము సమస్య కట్ కలిగి సార్లు సగం ఒక నిర్దిష్ట సంఖ్యలో. సార్లు ఆ సంఖ్య లాగ్ n. 

ఉత్తమ దృష్టాంతంలో ఏమిటి? బాగా, మొదటి సారి మనం midpoint లెక్కించేందుకు, మేము కోసం వెతుకుతున్నది. అన్ని మునుపటి బైనరీ శోధన మీద ఉదాహరణలు మేము కలిగి ఉంటే మేము, పైగా మారారు మూలకం 15 వెతుకుతున్న, మేము ఆ వెంటనే కనుగొన్నారు ఉండేది. చాలా ప్రారంభంలో ఉంది. ఆ midpoint ఉంది ఒక స్ప్లిట్ మొదటి ప్రయత్నాన్ని బైనరీ శోధన ఒక డివిజన్. 

కాబట్టి చెత్త కేసు బైనరీ శోధన నడుస్తుంది గణనీయంగా మెరుగైన ఇది లాగ్ n, లో చెత్త విషయంలో సరళ శోధన కంటే. ఉత్తమ సందర్భంలో, బైనరీ శోధన 1 ఒమేగా నడుస్తుంది. కాబట్టి బైనరీ శోధన చాలా ఉంది సరళ శోధన కంటే మెరుగైన, కానీ మీరు ప్రక్రియ పరిష్కరించుకోవాలి మీరు చెయ్యవచ్చు ముందు మొదటి మీ వ్యూహం క్రమబద్ధీకరించేందుకు బైనరీ శోధన శక్తిని పరపతి. 

నేను డౌ లాయిడ్ ఉన్నాను. ఈ CS 50.