從順序查找到二分查找課件

從順序查找到二分查找從順序查找到二分查找查找給定一個值Key，在含有n個元素的數(shù)組中找出等于給定值Key的元素。若找到，則查找成功，返回元素的信息或該元素在表中的位置；否則查找失敗，返回相關的指示信息。查找給定一個值Key，在含有n個元素的數(shù)組中找出等于給定值K順序查找從數(shù)組的一端開始，順序掃描數(shù)組，依次將掃描到的元素和給定值Key相比較。若當前掃描到的元素與Key相等，則查找成功；若掃描結(jié)束后，仍未找到元素等于Key的結(jié)點，則查找失敗。順序查找從數(shù)組的一端開始，順序掃描數(shù)組，依次將掃描到的元素和開始輸入待查找的值給變量keyi=1i<＝n？a(i)=key?Yi=i+1N輸出“找不到”N輸出“找到了”Y程序流程圖結(jié)束開始輸入待查找的值給變量keyi=1i<＝n？a(i)=k順序查找的效率n個元素的數(shù)組：最快：1次最慢：n次順序查找的效率n個元素的數(shù)組：思考如果數(shù)組是有序的，有沒有效率更高的算法？二分（對分）查找思考如果數(shù)組是有序的，有沒有效率更高的算法？二分（對分）查找二分查找（在一個升序的數(shù)組里）i＝1:j＝n:key=120確定查找的中點位置m=(i+j)\2將待找的Key與a(m)比較：若相等，則查找成功并返回此位置，查找結(jié)束。否則確定新的查找區(qū)間，繼續(xù)二分查找：若Key<a(m)，則要找的Key可能在m左邊的子數(shù)組a(1..m-1)中，故新的查找區(qū)間是左子數(shù)組a(1..m-1)中。若Key>a(m)，則要找的Key可能在m的右子數(shù)組a(m..n)中，即新的查找區(qū)間是右子表a(m+1..n)?！植檎遥ㄔ谝粋€升序的數(shù)組里）i＝1:j＝n:key2156789810110611012012513021567898101106110120125130Key=10621567898101106110120125130i=1j=10m=(i+j)\2=5i=m＋1＝6j=10m=8Key>a(m)Key<a(m)i=6j=m-1=7m=6Key=a(m)215678981011061101201251302156Key=6521567898101106110120125130i=1j=10m=5j=m-1=4mid=2Key<a(m)2156789810110611012012513021567898101106110120125130i=1i=3j=4Key>a(m)m=3j=m-1=2i>j還繼續(xù)嗎??Key=65215678981011061101201251二分查找i＝1，j＝n確定查找的中點位置m=(i+j)\2將待找的Key與a(m)比較：若相等，則查找成功并返回此位置，查找結(jié)束。否則確定新的查找區(qū)間，繼續(xù)二分查找：若Key<a(m)，則要找的Key可能在m左邊的子數(shù)組a(1..m-1)中，故新的查找區(qū)間是左子數(shù)組a(1..m-1)中。若Key>a(m)，則要找的Key可能在mid的右子數(shù)組a(m+1..n)中，即新的查找區(qū)間是右子表a(m+1..n)。……找不到時結(jié)束的條件：i>j二分查找i＝1，j＝n開始輸入待查找的值給變量keyi=1:j=ni<＝j？輸出“找不到”N輸出mY程序流程圖結(jié)束key<a(m)?NYj=m-1Ni=m+1Ym=(i+j)\2a(m)=key?開始輸入待查找的值給變量keyi=1:j=ni<＝j課堂實踐課堂實踐從順序查找到二分查找課件總結(jié)：順序查找與二分查找順序查找二分查找對數(shù)組的要求無要求必須是有序的假設數(shù)組是有序的前提比較的次數(shù)<=n<=int(log2n)+1查找效率低高總結(jié)：順序查找與二分查找順序查找二分查找對數(shù)組的要求無要求必從順序查找到二分查找從順序查找到二分查找查找給定一個值Key，在含有n個元素的數(shù)組中找出等于給定值Key的元素。若找到，則查找成功，返回元素的信息或該元素在表中的位置；否則查找失敗，返回相關的指示信息。查找給定一個值Key，在含有n個元素的數(shù)組中找出等于給定值K順序查找從數(shù)組的一端開始，順序掃描數(shù)組，依次將掃描到的元素和給定值Key相比較。若當前掃描到的元素與Key相等，則查找成功；若掃描結(jié)束后，仍未找到元素等于Key的結(jié)點，則查找失敗。順序查找從數(shù)組的一端開始，順序掃描數(shù)組，依次將掃描到的元素和開始輸入待查找的值給變量keyi=1i<＝n？a(i)=key?Yi=i+1N輸出“找不到”N輸出“找到了”Y程序流程圖結(jié)束開始輸入待查找的值給變量keyi=1i<＝n？a(i)=k順序查找的效率n個元素的數(shù)組：最快：1次最慢：n次順序查找的效率n個元素的數(shù)組：思考如果數(shù)組是有序的，有沒有效率更高的算法？二分（對分）查找思考如果數(shù)組是有序的，有沒有效率更高的算法？二分（對分）查找二分查找（在一個升序的數(shù)組里）i＝1:j＝n:key=120確定查找的中點位置m=(i+j)\2將待找的Key與a(m)比較：若相等，則查找成功并返回此位置，查找結(jié)束。否則確定新的查找區(qū)間，繼續(xù)二分查找：若Key<a(m)，則要找的Key可能在m左邊的子數(shù)組a(1..m-1)中，故新的查找區(qū)間是左子數(shù)組a(1..m-1)中。若Key>a(m)，則要找的Key可能在m的右子數(shù)組a(m..n)中，即新的查找區(qū)間是右子表a(m+1..n)?！植檎遥ㄔ谝粋€升序的數(shù)組里）i＝1:j＝n:key2156789810110611012012513021567898101106110120125130Key=10621567898101106110120125130i=1j=10m=(i+j)\2=5i=m＋1＝6j=10m=8Key>a(m)Key<a(m)i=6j=m-1=7m=6Key=a(m)215678981011061101201251302156Key=6521567898101106110120125130i=1j=10m=5j=m-1=4mid=2Key<a(m)2156789810110611012012513021567898101106110120125130i=1i=3j=4Key>a(m)m=3j=m-1=2i>j還繼續(xù)嗎??Key=65215678981011061101201251二分查找i＝1，j＝n確定查找的中點位置m=(i+j)\2將待找的Key與a(m)比較：若相等，則查找成功并返回此位置，查找結(jié)束。否則確定新的查找區(qū)間，繼續(xù)二分查找：若Key<a(m)，則要找的Key可能在m左邊的子數(shù)組a(1..m-1)中，故新的查找區(qū)間是左子數(shù)組a(1..m-1)中。若Key>a(m)，則要找的Key可能在mid的右子數(shù)組a(m+1..n)中，即新的查找區(qū)間是右子表a(m+1..n)?！也坏綍r結(jié)束的條件：i>j二分查找i＝1，j＝n開始輸入待查找的值給變量keyi=1:j=ni<＝j？輸出“找不到”N輸出mY程序流程圖結(jié)束key<a(m)?NYj=m-1Ni=m+1Ym=(i+j)\2a