Skalierung von Daten
Formen der Suche auf Arrays
Welche Formen der Suche auf Arrays können wir unterscheiden?
MTAwMDAw:rjnrTmLzrw/2a8olEAO3nS1cCLKpO7ef/79OKp3h3NY=:D9/+4zNmE6wF0y/O:rnrMVW9sc5VFHF701XGs4d/4C+wRCgUIqyO+hUxPk4CmNOL18Rnj3WaVcbqvjCVQnaBI9vZKmu3h2eD7g6glpE9SCdxBYqpUQTXQtrvUMQyGKXlEHFu5CloRWi6tFnrAUb+fVhKo9mZ5IWgw1kkm9wsmWBhr0becu/zGEz7kL4nBtWRWEJq1sg8Xotbn18tpGV8R
Konsequenzen der Skalierung
Welche Skalierungen von Daten unterscheiden wir im Kontext der Suche auf Arrays, und welche Konsequenzen ziehen sie jeweils für die Wahl des Suchverfahrens nach sich?
MTAwMDAw:LLeYiQUrN3PAX1QZHCSLzRwE1P9nx8LZGA2FozLQrKQ=:GlVBTlgd/2C6Z2l0:SEdK12wmvUr2UeoPuWTRmT+cGEwOgEpX9Witro7tVNBsXg1BKVBwlSC+A/x+aHJNEnP7Lmvk2qO1t+Kel66EygjiOoXJUz14czGIs/dulWA8yqVbS1RJGSC0k+XPdwAr+e5gft6s02QqtBM0eGqpTJz5sN5y7iwYdORsKOXfDvyXGBc+kQtGXx3MbIvbm87AE2iWiDb3Huz8xlMgY76AUgtFf0TjISs0iPzDRlr8SkdupYg8aWfmPN7r7upNA59r10/xDSalBQuiMML/aGTCXuKu5xmRDZzgd4UKkkCK4/2EKlVAnSr0B6bIALKR4jswHZYEbDcvBEMk7uxDGycIoLUIlUWM6svtYT0IyOK4uASDTUahDvVMa53c4l8AVvCNibJaeETQNsjNNylL9eE8PXbgjxs6bDV+NIucyi6CyN+nCvGqTyAWSbRPE7pqia+Pwyn83VBgfDHRmQ/8daW25huX2KandtCvoAZ3gFXIrmIvWEEgRymdhjZ0tNAUMc5p3VytawOdwtaVhRYqPHFlkLG9kQNJWopvXuAWbWE4vlaSMT0+egCgK+TA1Yo0NJXKKejPZeiR2N2zAoK7l/hnmAUAd9qQnGLOz1kQcYSxGD1+S450ElM9gol6pNvG7mQSsv/5UP6ZWsxYJXze5xsXiwvr8mGsb5VpcYnNqcovdUoik8s2s0S+nwcLEnR0fhXXqv1mCSzUKuCtSn3ykp/CzwWzvyE9X4vek89Gn5S8UcB3T/uDOkwM7oY8ppr+n33D7My6NzillkVYA19O6cTWS6LAFnsBceo7iGHdrHR6kwTd0CFfvro/GEyg+GSfXOrObsr/omEjyy/mqZHEwsyIuVTBzemtPtAHlUcyaiKMQ8p5Fyqrd80+7+XWVa4Y5c/sitp1G/1T/mFOHw==
Binäre Suche auf nominalen Daten
Warum ist eine binäre Suche auf nominal skalierten Daten prinzipiell unmöglich?
MTAwMDAw:hNqP3iUNMj1Jj5v2W1na4JMKjBegYsS2axtjCB4qjzk=:YUw6tTAQmRs87/FV:Pan8GpkwjTzSWFX59IZE9Hhszmn/LTclzXOkEBLpbXUgGEFFsoELK+Szp7aawClUXeaOo4tHO+r6OYp7TvXSBa1n+GWgAEoM7GTWlE8KW4Oy+TtiWnDpwGweiaKTp8cjLKIPm/7wSy+9pEzgNS2tB53WegxsnJu80wm1LocYxzwyV1x9ss55dJofmgh0xGAR+e65Shdj1PUllKDxbyr3rI6mAyxqtiNDKl265x0FJmF19N2Bv6W9uqjub+qkm5/9EtsmMYjCqA75pBVdRnJsSxuptxsVsQiuBywvoRJ1bVIjxaawgMH2lxcxtKl8lBt1J+3u5zzbK887p/feGzk0sRNi1+TwFkAAOdm3zGi/hWolA/bJQhPwPx8sGQ8Xlu90jQUbV91+6ZilmIzJsHUQkjtYFVEdFK5i92rdEH3OoB3DLnrGjv2K8IwlOtrxWjrUhyiCZlEPpssk0uwdYZ5YaNRtWVmsXQMnwnk7i25g796bY5jb6cnAw1v4L56AZejfccZWwtY2OH1clSNdMF1iQg0B2GDzotFCxP2hRB/I5nzNrv4JZ+wQ64lu2bP4Ya1R9sDjwsILOB3AbUAUVl/fl062Nle99nYU
Lineare und Binäre Suche
Komplexitätsvergleich
Vergleichen Sie die Laufzeitkomplexitäten (Worst Case, Average Case, Best Case) von linearer und binärer Suche hinsichtlich der Anzahl der Elementzugriffe.
MTAwMDAw:/hLBuo06mVp1rP9vTfivzWXQ4wPi9Cv8xacTMahAWIA=:zBo9PT77M9uOos8X:OKUsLmWQm1hacwz/ldOgYePnSJUr08dmJKJeGERHRue8VhpeJhqCUEvUaqp1p4D4I4yILmn74aK9+9gUBJhQ8ATM5PnkGfiKQ2tG5BZJKJBzpwa1sOR4/7RbU8faQwucVwONrh1SOcuC0U6RCu3YVqZ1GJ3cCLvfZNVvLevJYWHXm+ruioRWiidJB6ISEupjh29n4ruGtlJM3OJmu2j+30uutUUhr8dtrx4FqD/NOY5WSdtnbd/plNg2pcv+pS06o6sqazfsDUuI3hTTXWnz3DfrSONFYiVfazXVTgxP4AyALEuTzb4z7mbAv2+w02lp6L/7C3mNhNSk73FPEJkbAT2QQreVOCdM/ipMWL/1zT9TLKmsRJ3uwHYPB6g6UPsoGEKwjsEioJyOtzq6zBZnQ8/FJdBhoZ6OJMo7gfpb8fy7+Io2wwZdPswZvuCI/slsFIkRYqydo/X8do45/i+37gmmi8W0Cbcdjey4ZHx5qLPMIbyYXY2et9putR3rRFB0P6c4McKSXczHCjDW1+VFub+6+WDr0WfYAsV/km/K4Eh+Xqwi1V1zKJBfifCB29vifJQpAmyQ8r7BwuzgBRjrSFY2mOZs0dfD2G8cjOpfrEGhJtrcaGjnIBAo7MNciQ5d1Nt0dAn0Iy+EOeAfBlzyHFHb8UFgw9hTsdnqT99Hu9yWS5dTlnmM2xemxXg92bygRpQG3GmCqozElonNR/wrp4Hcv6DYc+5EmMuZ5jtb2KFnIFZGbM29HAMNY6mlo1Xqh1rykCDi0//qbQN+q+14ydbxRiw2k4+/jDjDBjzHn8soeI51oqGRdnJt1NxCwYIcWmGW4P4t8Ko2ehDwmKIHe6E8jdjS9DqFMUqh2M03tyF2So7qFTeUg61sadsDuspnH+RrPvqxoeVd0tCTEz1Urrr5+aE6F8+UOjue0TGj9k/B7JLMIH3dDm11MQpIhLK7GySQ7nNh+KWuWCxQiDt8R315RoSdS5/rcEP09rJ+fynHex4Ijprg/Zr8C3fp8vT+Koxe1q1hjxqTxx7TN6Mb/Czp7iqRXEna/2/+2JSJYPKrum9I8wnxmvpcLlD9R+hsmZWRaIa15KIN4t0B98oKMPkWEcsJsKs=
Voraussetzungen für die binäre Suche
Nennen Sie die zwingenden Voraussetzungen, unter denen die binäre Suche korrekt arbeitet.
MTAwMDAw:pTIIIp79RdmRZ6G1qG09XKgswyEeVT6IhVtJVpYG1pA=:pvmF2jEO1/sWIVzm:jJYHN5UuymuTHhADhXT6eQZVJffcwGL9o/rvAxo4IGb644c+R4JkURLuCyavNVyCj10n3dwqWfJFUc57QbqSLkb7Hxw7PgelnbiSsvu4Ob9r6WQS3OP2UIuFGF5kYO/ZG2BllSJVTMmY+vtRQAsXg/DmAeK/ju/1j+tN5uBKLzi+59YJDY/FZFUPJYjzpQVk2P4/sjtNBWULMp2M4RKsWpQduV2kYC8JMbDCEGt4b6D/VoN3OQ5X2VEPSch2X2Tc3BqkteZ9EoEm44Gj95v39GIShPbSz2Sd1hQK70ZvsOP5Zq0rR8a7+jGPfM/MDYlZk5wbs+uUDFDb/LnWAhTy98wNlk2BQtYTad6mwXyytEUQknWp90dqH4z5a5XvU9UuWohQoFZOrQH1iziH8ewnTM5ThgxrPE9iYDnHezIejRJPQDa1ISoCVjiV0j3PT8aOOS9tUQqiltIxj3Dlcq92UOX/0adk8V+lRa0hYTRhnqG+cItHqLVXz3RCwSF3/bf66ldrtYlKeC8l+42b4tn4x9AgVydixrQA6IjE
Worst Case der binären Suche
Unter welchen Umständen tritt der Worst Case der binären Suche ein?
(Mögliche Erweiterung in einer Klausur: Geben Sie ein konkretes Beispiel für ein Array der Länge :math:`n = 7` an.)
MTAwMDAw:EB7S1qXHlq7JFs1MbBsE9n0jYs0mvBsw2NXbRIRtgI4=:0c7ZGZeIawtCTSWq:FnwAdOo9mdVM/pAQJmD/vdRpwQb670YAzfo3g5/3yB4HqW+TIeGU6a9V0n/GgywZJglLCNubG/bgc7PQ7n46qfaDIhdQzZng8btYDMTOvMS1JO2siAn9YCBmrhUg+DB4ekuFlBIaFtZz+m9iZOcDXKYY9fIFM9BblIzE0LcxDw24zM9pVXNcKpEO7WYpk63JFZUVLwRhGadrT0RMic8ieJ18HUBU/9FyoT9+FJODvYD9TLXM71CkeDzFt5Qs7dNF2274eJSGcsM//WUQBIiXkocYAa+wpSz7766vl8q0yVs+ZfTzH77gdMIpXwW4BFbKgnA41PKzWDIYI0syRjPGwrWroK9fxGp2Y6NYZxMIqmCuaso6+FHM4m5E9psKqx1tHhxFStd2NfmHcxdcFsOhEcBD9HzconK9ObJP1zbHioVfrf7LJDVCE2SXf5Hpim3ao9vIAW5Kq5OTjU7Sab/Jj8b5sD+1qFvBz25NXfYs9A5XEImMgQL4fqeJym/a85tLPvWXRqExmbZfoYizhLeXXYzx2az15DacgPBbm11E14n1AAYNivN9/wfTyC6j/UpiXDKcoy7yXMYC59XdvBpHeqlUTQqrxeNt+rbd//cwAlfS3+i9clFsC4G0vb5qBAj/tZPwjOEcudYXVW/GR/SnTBYoTI7wauHurP4laTnBgu2PMZFtzXxb5jq957SJKLzTXzk6sjy5VQp2DQBjORRnjIF5aRicrw6YO8SCtBzFZ+oTpVdYHiBNTMrRMgvRQXhGOTUGYJ3vd8QB/F/awVf9z4wfGeK1rLCGAyLLPR3d4ldEwBCumPzDMECSx8uUOG0R0Mzv9MMp8xN+01jBbLObGltbJEUdGlFNMfQd92Y44LMsJDfjZjYyovvTPm91J0522l82buGSyy3/eOAeZ+/PWO646V4Mj6RTjhYOvwBhy+opVxIZnZRClPa7eYEAqCbRmG82u5qYAwXxVRkhQeNJaspmttMMIpVIfc3a7n1RhUqUdmrTRAXmTwDMRi/2n/iqU3rL7IzGVPLXYHEj1AFgaAT6HNoMWWNKiXZJkC99MiVnIu8evaVccO/AVu8WJwTjxyUkW0BbY+7ut/L0KSrh4FhLy91QNSjUGgpD20fyFZIx1Z6dCrb+jyO1GGBNt5u7wH8y/jNPKAW5z0XXR+PJvHk1izV6If4UXa1I+Et7AMCsZE2vaMJEoXFrcfUOpzv5u1fMUwXIjHdLnq57x3e59A7HjQ8M+whwLlflclHf9fjo2L6jY5NOiMbNh2QfF8gDfq3z2eFdRvBn7oH9mpCVT/qXpYai1rrGD7nhj4VtStABuIpiL2cWGC+x093DJkEYzyDTRRI+CaZYIfTJ2NZp6zjPvta8VY+Beg==
Grundidee und Annahmen
Ziel der Polynominterpolation
Was ist das Ziel der Polynominterpolation mittels Lagrange-Polynomen im Kontext der Suche auf Arrays?
MTAwMDAw:CohnRkrr4pBXUccQxjW4iEJAV1DGrqTfUoVm6cvhITA=:Gqv++BKhGb+fLbZa:NcHeNvlI4kzKMGJ+Q4Jwq0l9tWHBdqRrPG/3XRHYuapTYY3yBgHyuji1BR9ljuQSnsANeN8w1m35i2EQuccqOXjtrxin6dLVpNMTpjFGpyclXRTF87b7/Irl0JzxlJWrdvKz9pYggDMJGIs0tMAmJ35v6PPxcappvidqZK6N4AZ5Q4D4ZT4omM4a6ZAVZYqdX6IqXuZGQMENkzUjKJ8/RjnUFBbQ1WxZSno7yK0OzIRmbX14b4viGNWvcFVpfUeQbMLka/yMTUYy3hJ8HL6ybdBGBS4E1GBiddjUC+88FKHKWbTAK54zq61gNnRH0H+WNyNjjzJ76aeVqKdEf3KCQQZ+nEhdpP4YbGfiWfh6Bc5MHkEaleLpGFXjjwABHIVXCdmbGPkN6BUw+6sh8WtTWiqx581xUCOvX6hJCwYHaPPWTqeSSOhB5lbR6sXEtr1TjIrrDU5MpSdH0ECaxUWTc/6XtrYVIJC9anRQu049dxxzXc/zErpjNS55Ooy7ICaBxOUh8+hvSIUi9V1HENF38UN9mAKB7SDGr1xj/Qay2M3jan5A++JoIpS076G+mMJpMLIDP8xj/Hpp+L7qjPvrUSBa9ad6glAmzvBzzdNdmtvOdr+Ic0DUwkmTFvEYaN+xqew9Ef0hNrZK9Gkj8J7KxEhKFO5bXM7er8ApWWx9XYfx+5HVYokBM7KeIOmBihkJpuy1Z/8onLRfp6qnY/OrfZSYJA==
Grad des Interpolationspolynoms
Wie hängt der Grad des Lagrange-Interpolationspolynoms von der Anzahl der gegebenen Stützpunkte ab?
MTAwMDAw:70TgBemxW1DJ+oh4AulgcnocKzjeLGADYiYcoVX2RD4=:3hMfVpeDmjVLH7Jp:yGhvtVQEn0sbWWv8IksF13+evFoteGe6zzfQ5wPAUD9FQXQxUwVOzkPmu9C8qBR72osxZURtJbUpjQJwg/XYy+nUMtyTEgkCxMSGmONhdJWgP7HcCzITRS5aufZyLwjhLViQCSYaUNZ4XG+ncSefiti8EpcGd/cY0FCevrRi9ga9itlVN9UxB7EZxeFiQdB6gLkr+7SfYpF+/EAwfTrutMGVkA1AX5712FD4tvjv01t6bTd7G5nsqGu92lozZbjv6d1SwP55F+R58nflKvWEt0hTdh7fbyeMx/tLVO1baUSicwiY2BJKWGx763h5/pFY0sfeb2q5Bb1uSnlvX4dZuUoylOQdAk9qU429a1ee0FihwOE4yz8lLxYose4WEau9V6eGDAd6h2eS15DVzmCec9+BlHp2zuLTKkTdOOFJcZXcRaJfxONptYplkRs7gQOqnkQYJbkAkKtCy0V5WjQbIIwS7UFKSCM/zbDmACrhfPxN/A9CWFKrcmv0PL5Wyb8L17OMVvBgwHYiPMQ7h/ZEiTpiXjUvqeuph691l3c9sKu1Ctpc9whMfr4pgbX6mv48C1D7GCartFV32+D9YHgNDeV5DUPRLBx4fzubk63DruT1LdpmfaCFuhwqgAW8c+MwsCPpBT9g+HrBPKoCJpPdEA==
Wann ist Interpolation sinnvoll?
Unter welcher Annahme über die Verteilung der Daten ist eine interpolierende Suche der binären Suche überlegen? Wann kann sie schlechter sein?
MTAwMDAw:cLLZm6MVB22uEg4pJkRo5yAGUjCxc0pYoJMtyNmDUXk=:thq/fQBZLQo62US8:1ZNxJZx+2w/o3eAcixrv9l3Hz3w6M1rZHTR3P9FXlqQsplCpe3pbj6TDabDG+TVuDNSothPwUfzKn2ZH2A+EoFbb7tQZArVfaMQeqqFvsFK5I4dhHv7FfNRW+341okVM0qgxyCYwavAx5jHsWAb/UFg3IYEysn+DaYWo0Mmd1/ZuPLp04xjx2nnaOC9CuxlYpzyW333vYTvj4O6411OGZ3pcp8ZJLfxfIZbmyBPQ7+KsPCArXJFHhtcMIxqykgvIO7uMeZBqNHFfTnIts5sppa/GE/nn4Q6aDxK6a6q5Nt5FcsQ/EzMi+MN2P1cH+D2i8Pqu+YRD9N6NBZmkOpcTbGuh4erM3rc95zhZ/uTUxYsEPBsJIxfKI6SC7MXyInjhLsEEr33yapA20EG2THE+KSASzxpQSgVRFx5PrF02+XPpAqUOxSMxqozfJhB3pxxYvHz8r6rY5iL+LbaQOf3zWvU1OnNYwjihk6KDvhWYjOe33sC8zqNj5Cxmx64GKh6em4tRrvsYAFw/pglkym7MNwLL/fn/sd3RZXflL1Tn/VlxvlM2HCKFdHmNtnc66Yvbh5k5vTmXrfDNxbzLH2Q0Y+8s0kEEddahFBIO3Ccpzf2xLNNdVs7fYQ8rONLkkldk2i2FndlyZoSDyQaLe3qJ+AXanBKyKOKQSedrqqSB7x5Pn5HFFaRKYUpE6/pyg8C31wx69QnAUCozk6pFdgJ1we3yyG87q5d1IfEWbByJrHBkddOJZrLJziWfqHLf8j+qtQaX1GkTU4O76gXbURS1hGAkDEdzhvae+EB7MWG9i1bhHEOudndq1pG4BK5grb7v9GArrjPEtqNWXxYxeiDZi0nc57wfmN+hIrFqITCGnq3np/JrwrnrqwpVwYiNuNd3wT/T4jmputvsiXFQn6RxsXaNksyfyjLHBWxvA5pzdv951p6qo82RzUk8w0IQMEAVH+czwrPZB9RP7b5OVbPo/InI5IyS7RRG11lgCp6ebEBKLngkAM63c51+WhQOegLh/6SxXXTjr/5G8GaK6JE+10x7W7xecYEZ5Wy7kt1G9oWW4dWu2CJfzqe7cB1kFNBaHE0A7dAjAb56z2MgqdsMWVAh9wz9y5GMER8q
Korrektur der geschätzten Position
Im Algorithmus für die lineare interpolierende Suche wird die geschätzte Position pos mit folgender Zeile korrigiert:
pos := max(lower + 1, min(upper - 1, pos))
Warum ist diese Korrektur notwendig, obwohl die Daten sortiert sind?
MTAwMDAw:F8UeczLwjQY7WhHJ4kRUo7lSuW63IFmojaQ4ySyXtO8=:PSRN3TqCIozhNe5A:6Y5E/FtmuhvSnsxbmU7RjGtozTjyNr3ukoK5byadj1PGfY0KyfPLOtcEGQNXp0uDm7liLc1+OBbsgwW6OlPp0aFltyRFq/9tRS4NfsbN889pgn1u6NLX0LyIm2k4GPAWiVYkqz4s1jqvhXkG9p4tvxXbhJ/CzOerACaCMMI3U6hL1zsG/EJro+UZinnFMNHp50hTZ6xqp4yDdMIIOVanVkZ4i3ngY5LNmq424wC9X+fJEvbOy736PJ4Mih4KZzFJJZ3gnNJNRPrOxFrAyHBCsy134oFMoCv5O2ui5X9nWIjKhBP7b95I4LlmgTHEoiDsvk5sFr6jaYxhg2xvvTiJjpfkdV19vxBmYBvqYIa6CR+d0QxHxZv4O3cjD2/DUy0UZr4NmF8/lZ3m+VPcoF/Jx+OLJOy3BuzCcj96nUNFzeoIBIwommzacsO1bax2D5pvQKFepYiyKMVpAbYelPQJyoYGVBty5s/JAk6nWE+joRKBGUTqjNrFkKhbCg2CJAMZGatOB9UK17gHAAGt6labWIZXoe6+5qwbN4KNV7qM3Ai/ZMHtSUCYtuumGqsI1LvSuf+mXc2UqVF3fj7tMVL0NISeDT3rpWmP9MzcsYzAdPcyqq79Gy6ScpBB6l1hALOE/xLCsDx2oMTule5fKGvNl6uBP5WSDVUbDeWRCvRjj7q13NrlLWGeof4oqv5hxlau2xmAtnQUMclQX+RWdqLyaINZjc5U/OTqeGSr/NIIql71DORHVeMzL+DRBNGPXwc7EhkqJSjdKf/LLaYVB14Bu5wlTxSy7UDTbSK9PBpcOI/qjN5aKWR17TI2ePIzvD4ilVwOxkwDiDG9uG6qWVaclOZLkX+4t9H92BFy9DjEAvoaqKM62amCnYz2l4uNxctwBGwJCiaHpbaialOZEqJR4w2fCU/xXENQCCbS55etv9pvrHsiTf4Da+6B9m8eEq0pZN8ii4plmr6NjGtIbsH5ZelUjPkJTadZx1rJ6RdkvPSHqiZVYiTHUzz2PcajcX5zu90/se3ZCraFKb0DLR7W5VWD9uGuzxAZBWduDKyNlz7ZwXg5ia4w3dPb8WOCmzxb0kmqH0Uv8V48FRfS+pY63m3FdqIKa9cfb5SoJBSLqy7HvnHade8subh347D51oVqzT/YJdE=
Anwendung und Laufzeit
Wann ist exponentielle Suche sinnvoll?
Nennen Sie zwei Situationen, in denen die exponentielle Suche der reinen binären Suche vorzuziehen ist, und begründen Sie dies.
MTAwMDAw:R3NHf7xOl+NufGQXvZnGfRJbhiT48PWcWKeKScD+Cds=:RXtLIYr0kVYZrlPf:/Stx99yYm2koAWHHGKBnN+KMF8g4jOUJxWdFhj4PAbKp+8c4XOBLRe5BHTml1uHfD1vNWAz14LUzDPdRe/POdSKe/YwUGLCxVaxnaZ+bCP5leemPoz5zRKFRb7NQ1k7IjmYAjg0BjD1wIghjy2ONsZFu70dSmOcon+qAs2U2AsX5+DmMqyb4Y+sv7uQQZlsEkAwWQ7uHNW893kJB9vajCY+SVaBtZuw+gZ72eXokpQIujcllE6JlSPDkBpVzPBMuOKoVTa9YXwnALc0o0cYETYDvqYnkTyIWto3bsBnA86G1XxZuUiDcOTE4uk+moE9ImHdxl2aLdKxSLRk4SisrVyPJDOER2o65Kihl1p/7SmfGFNb5m0spl4IFRB2uFb+Cq0J59qhyi19MWU+eh8hwTGXMxlFzOQ+jtl2QlYPo9gcnUpyH1AvwtpGGoCt/zt512jlVhvfqYVTf7851zyh9a0t4M7CmQGkXT0ZT31mkHoeL3YfQLeCJYLcSlv3TBh8iTTC+FguNu5uthdvaiT8U2YxiojGlQGtkIjRIbtxrE5BKluinAZIYuiLj6qn3Vs6e35MT/Aqljbklpxrmd4qs2ws3zLXOmkTkM8et53Iv6BsH2of0G3kqEB8d/Zjpk8pJPAMIWZ1UfnMfcYoljmuG5sS3CZLC/nDUdtrBkD6z76h/su3qPKWYS3HUzNI2GFNKPCw79g8LXNhd3YGVZNQoaQhffDeuS3Rqvy6XVErLPKUfTbZ2K0rCToOem460q6C9+GunpaYz+NYxnaohSxXnYDxQEYBTBhqSVdAARch+3YvNP+NskJ6wovv7Y+LWLviGllyuS9NypO8Mbkd+NFKT6pSeKTO9WiYL1KvSC9DZAltktuNBqaKIOkxInMfHKFbKb8IwFvI+fXRP/EF+P+5fbWoGcKows8MqIPvFPZtcn8tRiAjP1R/Qd4pWRwWkGEIL8TpIQr6d6IbyuSnv9Q8agcNvDNqrIN9FZtHMJM3fX0O2XQv5xe6BaNLw348ByiYlMFvD1LxAHhjq4eeccszkTx3f1xNe/QmU7piTzf094/mdkdFzrPtDH2Y7dk0/Ei+YX3qEwZ+5V7LKDdd3oxDFlXYTfBU9C72D37vOy2WTFmxjQprw0wrRgbBYh7I6GgnqTxWKl6+heV9UGjo3X3odP8Ovcx3wwgVg2nk7hz3mlt8dYyxFggbEk+M3Py5bLtYxsXAfG6NOZcAO8tqyNuyo2ZmtXPuZHYX73yVuAAAaXWrpISOy2Aay4p57xD4=
Laufzeit der exponentiellen Suche
Wie lässt sich die Laufzeit der exponentiellen Suche asymptotisch ausdrücken, wenn sich der gesuchte Wert an Position \(i\) befindet?
MTAwMDAw:f4Xwr97ffJ6tZNzEPx+Pf6l8I6CtKWtezSXR2sq1gnI=:1XP4Ebbnz+XSzTca:rp/0ABhpSnuZAwsr3nCzoT6IMMvj57hT7lswFaOMQmt9YGoc8KrLSSW+SY3/ubf3W1cpyDkHSEB/w9uX/3zfzedfW3cN+fbJ0VzDIbv3bpo/x0XwSoCRX2LP5nlKUshWDG1+tI5Wiqe0yN9UMVIa7P8Kk74E04NQdpAaOwjNI8CUeq0LPKlc3ohbukHNlTkUz+3jcms0DVcp0GnptTjPzNZAOMN7eI9kYNPDdQr//d/je1KgVqumRx6UwZKgKw3M+9TIT2iIJr+RoJzoavNtFLiVjmdW0PiqlxJACe/ZaN9juSTRH758a4nFXy7McKK9YJXMkyLrUd9Xmfw/eKDbTCTOrn+8mMotRvTWsc/bpDiNiCPzMQy5zIGzZaTv7t72Uj1x4SpOIY2UbYsa1kXePJ9zZ7EQ5rLYX/fQEAI7n9VBvU/eSoisoVXv4i5f3PqxVSViFBzWJRHb+63GUhZiLEQAxR3ci+IVQyfuHW727QsouYpob8zUiLIE0m+uIe3serc+wk9x7lVhKq3Kz1xWvF8bw/OwywaJfkiii9jRHPUq4CrVT+5aqVqRsZ6+numi21/0wURUCLB5TMskmRbVyG/vkafBg8HJCcL69IQ0nAE5mNHFnqN7ity/LwpG+PY8txEAhKsrtCbTLIShbGVoSPXrFyYS2HMAfCX4DdyrjcPW64WFonD0RtdULQlwje0sP+FIZaRckJxK63DTR4XwEdDNDEaaIoI0XLotZJpFvZNIIz7oRTUvEO4oil7EuHXBm67VtbatyNTL4LT2+mVEC0ve3/FbSOotNJLxy6NAqLhoutWkbbCP5sbKEA4blIscFLbqzaQp+YETfh1+HS/cminr5Wb80aNatqt6CKcCJ2tdPKYc/OlF7gwSW2FeqEnHzg+0M5zgyTLAiVore38gVOCSNXWkKmDyrTsJetIflmNRppopzifsAb72DsQmzM1MddLX0QuQdQP3hfgw1FL+eFhvN9YYghX459/EyA8NVvxIwSkNGjX2rf1jGt3+fWZCB2F5Yu+VEl0Vjk/qTaDwRBbg2i07xrdeiAHxWbhRj+ia5/PJT2/U2yB5P1wV/mMO3WhXrhpDkRaZHxlbG4kPZh7oivmaEALUmPPoYuswNeoG0rwOlszpW4YO4NOn+F0UJbV4Z1ymRygXDB0VjhCvyKtvJCnmYRyiVfZ+JPc2wYFCaTY1jQ79lLKPdAsrnyWloy6+UertoiZ0nDQVubOYKwqoYyZIayoadrYUxQHPXEwdGVyA+hlLX1PL7PLycwnF0RCAt0bDLyzvwvlyn7cPU+t6nc4DY6rCB5XKfesjqtkZPgBVaasVn39CvQ5k