Binary Search and BSTs .edu

CSE 373: Data Structures and Algorithms

Binary Search and BSTs

Autumn 2018

Shrirang (Shri) Mare shri@cs.washington.edu

Thanks to Kasey Champion, Ben Jones, Adam Blank, Michael Lee, Evan McCarty, Robbie Weber, Whitaker Brand, Zora Fung, Stuart Reges, Justin Hsia, Ruth Anderson, and many others for sample slides and materials ...

Administrivia

Due dates: - HW2 Part 2 due Friday 11:59pm - HW1 grades will be released later today

CSE 373 AU 18 ? SHRI MARE

2

Modeling recursion: Unfolding Method

nX2 T (n) = C2 + C1

i=0

AAACEHicbZDLSsNAFIYn9VbjrerSzWARK6Ik2eimUOzGZYXeIIlhMp22QyeTMDMRSugjuPFV3LhQxK1Ld76N0zYLbf1h4OM/53Dm/GHCqFSW9W0UVlbX1jeKm+bW9s7uXmn/oC3jVGDSwjGLRTdEkjDKSUtRxUg3EQRFISOdcFSf1jsPREga86YaJ8SP0IDTPsVIaSsonXqu2azwM1iFnkyjIKNVa3Kf8QtnUg8cCM9hPbBNzw9KZevSmgkug51DGeRqBKUvrxfjNCJcYYakdG0rUX6GhKKYkYnppZIkCI/QgLgaOYqI9LPZQRN4op0e7MdCP67gzP09kaFIynEU6s4IqaFcrE3N/2puqvrXfkZ5kirC8XxRP2VQxXCaDuxRQbBiYw0IC6r/CvEQCYSVztDUIdiLJy9D27m0Nd855dpNHkcRHIFjUAE2uAI1cAsaoAUweATP4BW8GU/Gi/FufMxbC0Y+cwj+yPj8AR/LmXY=

CSE 373 AU 18 ? SHRI MARE

3

Modeling binary search recursion

Question: Find the closed form for T(N)

( T (n) =

AAACeHicbVHLbtswEKSUPlL15bTHXBZ109ooYEi6NJcWAXLpMQXsJIApGBS1solQlEBSTQxC39B/y60f0ktPpW0d2iQLEBjO7HDJYd5IYWwc/wrCvUePnzzdfxY9f/Hy1evBwZtzU7ea44zXstaXOTMohcKZFVbiZaORVbnEi/zqdKNf/EBtRK2mdt1gVrGlEqXgzHpqMfhJ59F0pMbwBajE0lIHNMelUI5pzdadk1x2EJ0uEvgAtMrrG3e9QtX5nfKehFKvpfAJplv7iBalZtypzqUd1WK5suMHjF8hiSiqoh8Cu85JRLPFYBhP4m3BfZD0YEj6OlsMbmlR87ZCZblkxsyTuLGZP9gKLrGLaGuwYfyKLXHuoWIVmsxtg+vgyDMFlLX2S1nYsv86HKuMWVe576yYXZm72oZ8SJu3tjzOnFBNa1Hx3aCylWBr2PwCFEIjt3LtAeNa+LsCXzGfnPV/FfkQkrtPvg/O00ni8fd0eBL3ceyTQ/KOjEhCPpMT8o2ckRnh5HdwGLwPjoI/IYQfw/GuNQx6z1vyX4XpX72VusY=

C1

n

C2 + T 2

when when

n=1 n>1

T (n) = C2 + T

AAACFnicbZDLSsNAFIYn9VbjrerSzWARWsSSdKMbodCNywq9QRPKZDpph04mYeZEKKFP4cZXceNCEbfizrdxello6w8DH/85hzPnDxLBNTjOt5Xb2Nza3snv2nv7B4dHheOTto5TRVmLxiJW3YBoJrhkLeAgWDdRjESBYJ1gXJ/VOw9MaR7LJkwS5kdkKHnIKQFj9QtXXs9ulmQZ3+J6v4ovcdMTLISSNwgVoZmcZtWpp/hwBGXb8/uFolNx5sLr4C6hiJZq9Atf3iCmacQkUEG07rlOAn5GFHAq2NT2Us0SQsdkyHoGJYmY9rP5WVN8YZwBDmNlngQ8d39PZCTSehIFpjMiMNKrtZn5X62XQnjjZ1wmKTBJF4vCVGCI8SwjPOCKURATA4Qqbv6K6YiYPMAkaZsQ3NWT16FdrbiG76vFmrOMI4/O0DkqIRddoxq6Qw3UQhQ9omf0it6sJ+vFerc+Fq05azlziv7I+vwB972cvg==

n 2

T (n) = C2 + C2 + T

AAACLnicbZBLSwMxEMezvl1fVY9egkWoCGW3CHoRCkXwqNCH0Cwlm2bb0Gx2SWaFsvQTefGr6EFQEa9+DNN2D74GQn75zwyT+YepFAY878VZWFxaXlldW3c3Nre2d0q7e22TZJrxFktkom9DargUirdAgOS3qeY0DiXvhKPGNN+549qIRDVhnPIgpgMlIsEoWKlXuiRdt1lRx/gCN3o1fIKJ5BFU5tycP0g/0pTlapKfTogWgyEcFxcmBLskcHulslf1ZoH/gl9AGRVx3Ss9kX7CspgrYJIa0/W9FIKcahBM8olLMsNTykZ0wLsWFY25CfLZuhN8ZJU+jhJtjwI8U7935DQ2ZhyHtjKmMDS/c1Pxv1w3g+g8yIVKM+CKzQdFmcSQ4Kl3uC80ZyDHFijTwv4VsyG13oB1eGqC/3vlv9CuVX3LN7Vy3SvsWEMH6BBVkI/OUB1doWvUQgzdo0f0it6cB+fZeXc+5qULTtGzj36E8/kFzNSkww==

n 4

T (n) = C2 + C2 + C2 + T

AAACNHicbZDLSgMxFIYz3h1vVZdugkVoEcpMN3YjFLoR3Cj0IjRDyaSZNpjJDMkZoQx9KDc+iBsRXCji1mcwbWfh7UCSL/85h+T8YSqFAc97dpaWV1bX1jc23a3tnd290v5B1ySZZrzDEpnom5AaLoXiHRAg+U2qOY1DyXvhbWuW791xbUSi2jBJeRDTkRKRYBSsNChdkr7brqgqPsetQR2fFjuRPILKgtuLCxlGmrJcTfPGlGgxGkO1ODAh2CWBOyiVvZo3D/wX/ALKqIirQemRDBOWxVwBk9SYvu+lEORUg2CST12SGZ5SdktHvG9R0ZibIJ8PPcUnVhniKNF2KcBz9XtHTmNjJnFoK2MKY/M7NxP/y/UziBpBLlSaAVds8VCUSQwJnjmIh0JzBnJigTIt7F8xG1PrDVifZyb4v0f+C916zbd8XS83vcKODXSEjlEF+egMNdEFukIdxNA9ekKv6M15cF6cd+djUbrkFD2H6Ec4n1/zgKZC

n 8

T (n) =

AAACd3icbVFLb9QwEHZCgRJeW7i1h1osVFtVqpK9lAtSpV56LNJuW2kdVo4z2bXqOJE9Qays8BP4cdz4H1y44ezm0NdItj5/883DM1mtpMU4/hOET7aePnu+/SJ6+er1m7eDnXeXtmqMgKmoVGWuM25BSQ1TlKjgujbAy0zBVXZz1vmvvoOxstITXNWQlnyhZSEFR0/NB7/YLGIZLKR23Bi+ap0Sqo0mI31Iv9ADyhqdg8kMF+DO5mN6RDc3yyu0m1frZUc/J0xBgSOWF17rdOvG37BlRi6WeEgZo5HPVWbVD4cUZQm2i2IsYqDzvnLE0mg+GMbH8droQ5D0YEh6u5gPfvtORFOCRqG4tbMkrjH1GVEKBT5nY6Hm4oYvYOah5r506tZza+knz+S0qIw/GumavR3heGntqsy8suS4tPd9HfmYb9Zg8Tl1UtcNghabQkWjKFa0WwLNpQGBauUBF0b6XqlYcj849KvqhpDc//JDcDk+Tjz+Oh6exv04tske+UBGJCEn5JSckwsyJYL8DXaDYfAx+BfuhwfhaCMNgz7mPbljYfIf3Fu6Ug==

C| 2 + C2 {+z ? ? ? + C}2 t times

n + T 2t

We want to find a t such that

n 2t

AAACAXicbZDLSsNAFIZPvNZ4i7oR3AwWwVVJutGNUHDjsoK9QBLLZDpph04mYWYilFA3voobF4q49S3c+TZO2yy09YeBj/+cw5nzRxlnSrvut7Wyura+sVnZsrd3dvf2nYPDtkpzSWiLpDyV3QgrypmgLc00p91MUpxEnHai0fW03nmgUrFU3OlxRsMEDwSLGcHaWD3nOPDtoB9LTAoxKer3eoKukGcHYc+pujV3JrQMXglVKNXsOV9BPyV5QoUmHCvle26mwwJLzQinEzvIFc0wGeEB9Q0KnFAVFrMLJujMOH0Up9I8odHM/T1R4ESpcRKZzgTroVqsTc3/an6u48uwYCLLNRVkvijOOdIpmsaB+kxSovnYACaSmb8iMsQmDm1Cs00I3uLJy9Cu1zzDt/Vqwy3jqMAJnMI5eHABDbiBJrSAwCM8wyu8WU/Wi/VufcxbV6xy5gj+yPr8AV+YlXc=

=1

Solving for t we get

t AAAB+nicbZDLSsNAFIZP6q3GW6pLN4NFcFWSbnQjFNy4rGAv0IQwmU7aoZNJmJkoJfZR3LhQxK1P4s63cdpmoa0/DHz85xzOmT/KOFPadb+tysbm1vZOddfe2z84PHJqx12V5pLQDkl5KvsRVpQzQTuaaU77maQ4iTjtRZObeb33QKViqbjX04wGCR4JFjOCtbFCp+YPbI2uEU9HYRMJ2w9Cp+423IXQOngl1KFUO3S+/GFK8oQKTThWauC5mQ4KLDUjnM5sP1c0w2SCR3RgUOCEqqBYnD5D58YZojiV5gmNFu7viQInSk2TyHQmWI/Vam1u/lcb5Dq+CgomslxTQZaL4pwjnaJ5DmjIJCWaTw1gIpm5FZExlphok5ZtQvBWv7wO3WbDM3zXrLfcMo4qnMIZXIAHl9CCW2hDBwg8wjO8wpv1ZL1Y79bHsrVilTMn8EfW5w9syZIX

=

log2n

T (n)

AAACB3icbZBPS8MwGMbT+W/Wf1WPggSHMBFG24tehMEuHidsc9CWkmbpFpamJUmFUXbz4lfx4kERr34Fb34bs60H3Xwg8Mvzvi/J+0QZo1LZ9rdRWVvf2Nyqbps7u3v7B9bhUU+mucCki1OWin6EJGGUk66iipF+JghKIkbuo3FrVr9/IELSlHfUJCNBgoacxhQjpa3QOvU9s1PnF/AGtkIXQpYOQ5fDS31zTD8IrZrdsOeCq+CUUAOl2qH15Q9SnCeEK8yQlJ5jZyookFAUMzI1/VySDOExGhJPI0cJkUEx32MKz7UzgHEq9OEKzt3fEwVKpJwkke5MkBrJ5drM/K/m5Sq+DgrKs1wRjhcPxTmDKoWzUOCACoIVm2hAWFD9V4hHSCCsdHSmDsFZXnkVem7D0Xzn1pp2GUcVnIAzUAcOuAJNcAvaoAsweATP4BW8GU/Gi/FufCxaK0Y5cwz+yPj8AdzblWo=

=

C2log2n + C1

CSE 373 AU 18 ? SHRI MARE

4

Storing Sorted Items in an Array

get() ? O(logn) put() ? O(n) remove() ? O(n)

Can we do better with insertions and removals?

CSE 373 SP 18 - KASEY CHAMPION

5

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download