java python算法

什么是搜索算法？ (What is a Search Algorithm?)

This kind of algorithm looks at the problem of re-arranging an array of items in ascending order. The two most classical examples of that is the binary search and the merge sort algorithm.

這種算法著眼于以升序重新排列項目數組的問題。最經典的兩個例子是二進制搜索和合并排序算法。

指數搜索 (Exponential Search)

Exponential Search, also known as finger search, searches for an element in a sorted array by jumping ?2^i elements in every iteration, where i represents the value of loop control variable, and then verifying if the search element is present between the last jump and the current jump.

指數搜索(也稱為手指搜索)通過在每次迭代中跳過2^i元素來搜索排序數組中的元素，其中i代表循環控制變量的值，然后驗證在最后一次跳轉之間是否存在搜索元素和當前的跳躍。

復雜性最壞的情況 (Complexity Worst Case)

O(log(N)) Often confused because of the name, the algorithm is named so not because of the time complexity. The name arises as a result of the algorithm jumping elements with steps equal to exponents of 2

O(log(N))通常由于名稱而感到困惑，因此命名該算法并不是因為時間復雜。該名稱的出現是由于算法以等于2的指數步長跳躍元素

腳步 (Steps)

Jump the array ?2^i ?elements at a time searching for the condition ?Array[2^(i-1)] < valueWanted < Array[2^i] . If ?2^i ?is greater than the lenght of array, then set the upper bound to the length of the array.
一次跳轉數組2^i元素，以查找條件Array[2^(i-1)] < valueWanted < Array[2^i] 。如果2^i大于數組的長度，則將數組的長度設置為上限。
Do a binary search between ?Array[2^(i-1)] ?and ?Array[2^i]
在Array[2^(i-1)]和Array[2^i]之間進行二進制搜索

碼 (Code)

// C++ program to find an element x in a
// sorted array using Exponential search.
#include <bits/stdc++.h>
using namespace std;int binarySearch(int arr[], int, int, int);// Returns position of first ocurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{// If x is present at firt location itselfif (arr[0] == x)return 0;// Find range for binary search by// repeated doublingint i = 1;while (i < n && arr[i] <= x)i = i*2;//  Call binary search for the found range.return binarySearch(arr, i/2, min(i, n), x);
}// A recursive binary search function. It returns
// location of x in  given array arr[l..r] is
// present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{if (r >= l){int mid = l + (r - l)/2;// If the element is present at the middle// itselfif (arr[mid] == x)return mid;// If element is smaller than mid, then it// can only be present n left subarrayif (arr[mid] > x)return binarySearch(arr, l, mid-1, x);// Else the element can only be present// in right subarrayreturn binarySearch(arr, mid+1, r, x);}// We reach here when element is not present// in arrayreturn -1;
}int main(void)
{int arr[] = {2, 3, 4, 10, 40};int n = sizeof(arr)/ sizeof(arr[0]);int x = 10;int result = exponentialSearch(arr, n, x);(result == -1)? printf("Element is not present in array"): printf("Element is present at index %d", result);return 0;
}

搜索鏈接列表與數組 (Searching Linked Lists Versus Arrays)

Suppose you have to search for an element in an ?unsorted ?linked list and array. In that case, you need to do a linear search (remember, unsorted). Doing a linear search for an element in either data structure will be an O(n) operation.

假設您必須在未排序的鏈表和數組中搜索元素。在這種情況下，您需要進行線性搜索(記住，未排序)。對任一數據結構中的元素進行線性搜索將是O(n)操作。

Now if you have a ?sorted ?linked list and array, you can still search in both the data structures in O(log n) time using Binary Search. Although, it will be a bit tedious to code while using linked lists.

現在，如果您有一個排序的鏈表和數組，您仍然可以使用Binary Search在O(log n)時間內在兩個數據結構中進行搜索。雖然，在使用鏈表時進行編碼有點繁瑣。

Linked lists are usually preferred over arrays where insertion is a frequent operation. It's easier to insert in linked lists as only a pointer changes. But to insert in an array (the middle or beginning), you need to move all the elements after the one that you insert. Another place where you should use linked lists is where size is uncertain (you don't know the size when you are starting out), because arrays have fixed size.

通常，鏈表優于插入是頻繁操作的數組。只需更改指針，插入鏈接列表就更容易了。但是要插入數組(中間或開頭)，您需要將所有元素移到要插入的元素之后。另一個應該使用鏈表的地方是大小不確定(因為數組的大小是固定的，所以您不知道大小)。

Arrays do provide a few advantages over linked lists:

與鏈接列表相比，數組確實具有一些優勢：

Random access
隨機訪問
Less memory as compared to linked lists
與鏈接列表相比，內存更少
Arrays have better cache locality thus providing better performance
陣列具有更好的緩存位置，從而提供更好的性能

It completely depends on the use case for whether arrays or linked lists are better.

對于數組還是鏈表是否更好，這完全取決于用例。

線性搜尋 (Linear Search)

Suppose you are given a list or an array of items. You are searching for a particular item. How do you do that?

假設給您一個列表或項目數組。您正在搜索特定項目。你是怎樣做的？

Find the number 13 in the given list.

在給定列表中找到數字13。

You just look at the list and there it is!

您只要看一下清單就可以了！

Now, how do you tell a computer to find it.

現在，如何告訴計算機找到它。

A computer cannot look at more than the value at a given instant of time. So it takes one item from the array and checks if it is the same as what you are looking for.

在給定的時間，計算機所看到的值不能超過該值。因此，它從數組中取出一項，并檢查它是否與您要查找的項相同。

The first item did not match. So move onto the next one.

第一項不匹配。因此，移至下一個。

And so on...

等等...

This is done till a match is found or until all the items have been checked.

完成此操作，直到找到匹配項或檢查了所有項目。

In this algorithm, you can stop when the item is found and then there is no need to look further.

在此算法中，您可以在找到項目后停止，然后無需進一步查找。

So how long would it take to do the linear search operation? In the best case, you could get lucky and the item you are looking at maybe at the first position in the array! But in the worst case, you would have to look at each and every item before you find the item at the last place or before you realize that the item is not in the array.

那么線性搜索操作需要多長時間？在最好的情況下，您可能會很幸運，并且您正在尋找的物品可能在陣列的第一位置！但是在最壞的情況下，您必須先查看每個項目，然后才能找到該項目的最后一位，或者您意識到該項目不在數組中。

The complexity therefore of the linear search is O(n).

因此，線性搜索的復雜度為O(n)。

If the element to be searched presides on the the first memory block then the complexity would be O(1).

如果要搜索的元素位于第一個存儲塊中，則復雜度將為O(1)。

The code for a linear search function in JavaScript is shown below. This function returns the position of the item we are looking for in the array. If the item is not present in the array, the function would return null.

JavaScript中的線性搜索功能代碼如下所示。此函數返回我們要查找的項目在數組中的位置。如果該項目不存在于數組中，則該函數將返回null。

int linearSearch(int arr[], int num)
{int len = (int)( sizeof(arr) / sizeof(arr[0]);int *a = arr;for(int i = 0; i < len; i++){if(*(a+i) == num) return i;}return -1;
}

JavaScript中的示例 (Example in JavaScript)

function linearSearch(arr, item) {// Go through all the elements of arr to look for item.for (var i = 0; i < arr.length; i++) {if (arr[i] === item) { // Found it!return i;}}// Item not found in the array.return null;
}

Ruby中的示例 (Example in Ruby)

def linear_search(target, array)counter = 0while counter < array.lengthif array[counter] == targetreturn counterelsecounter += 1endendreturn nil
end

C ++中的示例 (Example in C++)

int linear_search(int arr[],int n,int num)
{for(int i=0;i<n;i++){if(arr[i]==num)return i;}// Item not found in the arrayreturn -1; 
}

Python范例 (Example in Python)

def linear_search(array, num):for index, element in enumerate(array):if element == num:return indexreturn -1

Swift中的示例 (Example in Swift)

func linearSearch(for number: Int, in array: [Int]) -> Int? {for (index, value) in array.enumerated() {if value == number { return index } // return the index of the number}return nil // the number was not found in the array
}

Java范例 (Example in Java)

int linearSearch(int[] arr, int element)
{for(int i=0;i<arr.length;i++){if(arr[i] == element)return i;}return -1;
}

PHP中的示例 (Example in PHP)

function linear_search($arr=[],$num=0)
{$n = count($arr);   for( $i=0; $i<$n; $i++){if($arr[$i] == $num)return $i;}// Item not found in the arrayreturn -1; 
}$arr = array(1,3,2,8,5,7,4,0);
print("Linear search result for 2: ");
echo linear_search($arr,2);

全局線性搜索 (Global Linear Search)

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

如果要搜索一個元素的多次出現怎么辦？例如，您想查看數組中有5個數字。

Target = 5

目標= 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

數組= [1、2、3、4、5、6、5、7、8、9、5]

This array has 3 occurances of 5s and we want to return the indexes (where they are in the array) of all of them. This is called global linear search. You will need to adjust your code to return an array of the index points at which it finds the target element. When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match the code will continue to move on to the next element in the array by adding 1 to the counter.

該數組有3個5s出現，我們想返回所有它們的索引(它們在數組中的位置)。這稱為全局線性搜索。您將需要調整代碼以返回在其找到目標元素的索引點的數組。當找到與目標匹配的索引元素時，索引點(計數器)將添加到結果數組中。如果不匹配，代碼將通過向計數器加1繼續移動到數組中的下一個元素。

def global_linear_search(target, array)counter = 0results = []while counter < array.lengthif array[counter] == targetresults << countercounter += 1elsecounter += 1endendif results.empty?return nilelsereturn resultsend
end

為什么線性搜索效率不高 (Why linear search is not efficient)

There is no doubt that linear search is simple but because it compares each element one by one, it is time consuming and hence not very efficient. If we have to find a number from say, 1000000 numbers and number is at the last location, linear search technique would become quite tedious. So, also learn about binary search, exponential search, etc. which are much more efficient than linear search.

毫無疑問，線性搜索很簡單，但是由于它逐一比較每個元素，因此很耗時，因此效率不高。如果必須從一個數字中找到一個數字，即1000000個數字并且數字位于最后一個位置，則線性搜索技術將變得非常乏味。因此，還要了解比線性搜索有效得多的二進制搜索，指數搜索等。

二元搜尋 (Binary Search)

A binary search locates an item in a sorted array by repeatedly dividing the search interval in half.

二進制搜索通過將搜索間隔重復分成兩半來找到排序數組中的項。

How do you search a name in a telephone directory?

您如何在電話簿中搜索姓名？

One way would be to start from the first page and look at each name in the phonebook till we find what we are looking for. But that would be an extremely laborious and inefficient way to search.

一種方法是從第一頁開始，查看電話簿中的每個名稱，直到找到所需的內容。但這將是一種極其費力且效率低下的搜索方式。

Because we know that names in the phonebook are sorted alphabetically, we could probably work along the following steps:

因為我們知道電話簿中的名稱是按字母順序排序的，所以我們可以按照以下步驟進行操作：

Open the middle page of the phonebook
打開電話簿的中間頁
If it has the name we are looking for, we are done!
如果它具有我們想要的名稱，我們就完成了！
Otherwise, throw away the half of the phonebook that does not contain the name
否則，請丟棄電話簿中不包含姓名的一半
Repeat until you find the name or there are no more pages left in the phonebook
重復直到找到名稱或電話簿中沒有剩余頁面為止

[

]

Time complexity: As we dispose off one part of the search case during every step of binary search, and perform the search operation on the other half, this results in a worst case time complexity of ?O ( log2N ). The best case occurs when the element to be found is in the middle of the list. The best case time complexity is ?O ( 1 ).

時間復雜度：由于我們在二分搜索的每一步中都放置了一部分搜索用例，而在另一半上執行了搜索操作，因此這導致了最差的時間復雜度O ( log2N )。當要找到的元素在列表的中間時，將發生最佳情況。最佳情況下時間復雜度為O ( 1 )。

Space complexity: Binary search takes constant or ?O ( 1 ) space meaning that we don't do any input size related variable defining.

空間復雜度：二進制搜索占用常量或O ( 1 )空間，這意味著我們不進行任何與輸入大小相關的變量定義。

for small sets linear search is better but in larger ones it is way more efficient to use binary search.

對于小集合，線性搜索更好，但在大集合中，使用二進制搜索會更有效。

In detail, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

詳細地說，您可以將N除以2多少次，直到得到1？本質上講，進行二進制搜索(將元素減半)，直到找到它為止。用公式可以是：

1 = N / 2^x

Multiply by 2x:

乘以2倍：

2^x = N

Now do the log2:

現在執行log2：

log2(2^x)   = log2 N
x * log2(2) = log2 N
x * 1       = log2 N

This means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element.

這意味著您可以將日志除以N次，直到將所有內容都除。這意味著您必須除以log N(“執行二進制搜索步驟”)，直到找到您的元素。

O ( log2N ) is such so because at every step half of the elements in the data set are gone which is justified by the base of the logarithmic function.

O ( log2N )之所以如此，是因為在每一步中，數據集中的元素的一半都消失了，這由對數函數的基數證明是正確的。

This is the binary search algorithm. It is elegant and efficient but for it to work correctly, the array must be ?sorted .

這是二進制搜索算法。它既優雅又高效，但是要使其正常工作，必須對數組進行排序。

Find 5 in the given array of numbers using binary search.

使用二進制搜索在給定的數字數組中找到5。

Mark low, high and mid positions in the array.

在陣列中標記低，高和中位置。

Compare the item you are looking for with the middle element.

將您要查找的項目與中間元素進行比較。

Throw away the left half and look in the right half.

扔掉左半部分，然后看向右半部分。

Again compare with the middle element.

再次與中間元素進行比較。

Now, move to the left half.

現在，移至左半部分。

The middle element is the item we were looking for!

中間元素是我們正在尋找的物品！

The binary search algorithm takes a divide-and-conquer approach where the array is continuously divided until the item is found or until there are no more elements left for checking. Hence, this algorithm can be defined recursively to generate an elegant solution.

二進制搜索算法采用分而治之的方法，在該方法中，數組將連續劃分，直到找到該項目或直到不再有要檢查的元素為止。因此，可以遞歸地定義該算法以生成優雅的解決方案。

The two base cases for recursion would be:

遞歸的兩個基本情況是：

No more elements left in the array
數組中沒有剩余元素
Item is found
找到項目

The Power of Binary Search in Data Systems (B+ trees): Binary Search Trees are very powerful because of their O(log n) search times, second to the hashmap data structure which uses a hashing key to search for data in O(1). It is important to understand how the log n run time comes from the height of a binary search tree. If each node splits into two nodes, (binary), then the depth of the tree is log n (base 2).. In order to improve this speed in Data System, we use B+ trees because they have a larger branching factor, and therefore more height. I hope this short article helps expand your mind about how binary search is used in practical systems.

數據系統中二進制搜索的力量(B +樹)：二進制搜索樹由于其O(log n)搜索時間而非常強大，僅次于使用哈希鍵在O(1)中搜索數據的哈希圖數據結構。。重要的是要了解log n運行時間如何來自二進制搜索樹的高度。如果每個節點都分成兩個節點(二進制)，則樹的深度為log n(以2為底)。為了提高數據系統中的速度，我們使用B +樹，因為它們的分支因子更大，并且因此更高的高度。我希望這篇簡短的文章可以幫助您擴大對實際系統中二進制搜索的使用方式的了解。

The code for recursive binary search is shown below:

遞歸二進制搜索的代碼如下所示：

JavaScript實現 (JavaScript implementation)

function binarySearch(arr, item, low, high) {if (low > high) { // No more elements in the array.return null;}// Find the middle of the array.var mid = Math.ceil((low + high) / 2);if (arr[mid] === item) { // Found the item!return mid;}if (item < arr[mid]) { // Item is in the half from low to mid-1.return binarySearch(arr, item, low, mid-1);}else { // Item is in the half from mid+1 to high.return binarySearch(arr, item, mid+1, high);}
}var numbers = [1,2,3,4,5,6,7];
print(binarySearch(numbers, 5, 0, numbers.length-1));

Here is another implementation in JavaScript:

這是JavaScript的另一種實現：

function binary_search(a, v) {function search(low, high) {if (low === high) {return a[low] === v;} else {var mid = math_floor((low + high) / 2);return (v === a[mid])||(v < a[mid])? search(low, mid - 1): search(mid + 1, high);}}return search(0, array_length(a) - 1);
}

Ruby實現 (Ruby implementation)

def binary_search(target, array)sorted_array = array.sortlow = 0high = (sorted_array.length) - 1while high >= lowmiddle = (low + high) / 2if target > sorted_array[middle]low = middle + 1elsif target < sorted_array[middle]high = middle - 1elsereturn middleendendreturn nil
end

C中的例子 (Example in C)

int binarySearch(int a[], int l, int r, int x) {if (r >= l){int mid = (l + (r - l))/2;if (a[mid] == x)return mid;if (arr[mid] > x)return binarySearch(arr, l, mid-1, x);return binarySearch(arr, mid+1, r, x);}return -1;
}

Python實現 (Python implementation)

def binary_search(arr, l, r, target):if r >= l:mid = (l + (r - l))/2if arr[mid] == target:return midelif arr[mid] > target:return binary_search(arr, l, mid-1, target)else:return binary_search(arr, mid+1, r, target)else:return -1

C ++中的示例 (Example in C++)

Recursive approach!

遞歸的方法！

// Recursive approach in C++
int binarySearch(int arr[], int start, int end, int x)
{if (end >= start){int mid = (start + (end - start))/2;if (arr[mid] == x)return mid;if (arr[mid] > x)return binarySearch(arr, start, mid-1, x);return binarySearch(arr, mid+1, end, x);}return -1;
}

Iterative approach!

迭代的方法！

int binarySearch(int arr[], int start, int end, int x)
{while (start <= end){int mid = (start + (end - start))/2;if (arr[mid] == x)return mid;if (arr[mid] < x)start = mid + 1;elseend = mid - 1;}return -1;
}

Swift中的示例 (Example in Swift)

func binarySearch(for number: Int, in numbers: [Int]) -> Int? {var lowerBound = 0var upperBound = numbers.countwhile lowerBound < upperBound {let index = lowerBound + (upperBound - lowerBound) / 2if numbers[index] == number {return index // we found the given number at this index} else if numbers[index] < number {lowerBound = index + 1} else {upperBound = index}}return nil // the given number was not found
}

Java范例 (Example in Java)

// Iterative Approach in Java
int binarySearch(int[] arr, int start, int end, int element)
{while(start <= end){int mid = start + ( end - start ) / 2;if(arr[mid] == element)return mid;if(arr[mid] < element)start = mid+1;elseend = mid-1;}return -1;
}

// Recursive Approach in Java
int binarySearch(int[] arr, int start,int end , int element)
{if (end >= start){int mid = start + ( end - start ) / 2;if(arr[mid] ==  element)return mid;if(arr[mid] < element)return binarySearch( arr , mid + 1 , end , element );elsereturn binarySearch( arr, start, mid - 1 , element);}return -1;
}