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