Java、Python、およびC ++の例で説明されている検索アルゴリズム

検索アルゴリズムとは何ですか?

この種のアルゴリズムは、アイテムの配列を昇順で再配置する問題を調べます。その最も古典的な2つの例は、バイナリ検索とマージソートアルゴリズムです。

指数検索

指検索とも呼ばれる指数検索は、2^i反復ごとに要素をジャンプすることにより、並べ替えられた配列内の要素を検索し  ます。ここで、iはループ制御変数の値を表し、検索要素が最後のジャンプと現在のジャンプの間に存在するかどうかを確認します。ジャンプ。

複雑さの最悪の場合

O(log(N))名前が原因で混乱することがよくありますが、アルゴリズムの名前は時間の複雑さのためではありません。この名前は、2の指数に等しいステップで要素をジャンプするアルゴリズムの結果として生じます。

ステップ

  1. 2^i  条件を検索しながら、一度に配列要素をジャンプし  ます  Array[2^(i-1)] < valueWanted < Array[2^i]2^i  が配列の長さより大きい場合  は、上限を配列の長さに設定します。
  2. Array[2^(i-1)]  との間で二分探索  を行う  Array[2^i]

コード

// C++ program to find an element x in a // sorted array using Exponential search. #include  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 itself if (arr[0] == x) return 0; // Find range for binary search by // repeated doubling int 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 // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it // can only be present n left subarray if (arr[mid] > x) return binarySearch(arr, l, mid-1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid+1, r, x); } // We reach here when element is not present // in array return -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; } 

リンクリストと配列の検索

ソート  されていないリンクリストと配列で要素を検索する必要があるとします  。その場合、線形検索を実行する必要があります(ソートされていないことを忘れないでください)。いずれかのデータ構造の要素を線形検索すると、O(n)演算になります。

これで、  ソート  されたリンクリストと配列がある場合でも、バイナリ検索を使用して、O(log n)時間で両方のデータ構造を検索できます。ただし、リンクリストを使用しているときにコーディングするのは少し面倒です。

リンクリストは通常​​、挿入が頻繁に行われる配列よりも優先されます。ポインタのみが変更されるため、リンクリストに挿入する方が簡単です。ただし、配列(中央または先頭)に挿入するには、挿入した要素の後にすべての要素を移動する必要があります。リンクリストを使用する必要があるもう1つの場所は、配列のサイズが固定されているため、サイズが不確実な場合(最初はサイズがわからない場合)です。

配列には、リンクリストに比べていくつかの利点があります。

  1. ランダムアクセス
  2. リンクリストと比較してメモリが少ない
  3. 配列はキャッシュの局所性が優れているため、パフォーマンスが向上します

配列とリンクリストのどちらが優れているかは、ユースケースに完全に依存します。

線形探索

リストまたはアイテムの配列が与えられたとします。あなたは特定のアイテムを探しています。どうやってそれをしますか?

与えられたリストで番号13を見つけます。

線形探索1

リストを見るだけで、そこにあります!

線形探索2

では、どのようにしてコンピュータにそれを見つけるように指示しますか。

コンピューターは、特定の時点で値を超える値を確認することはできません。したがって、配列から1つの項目を取得し、それが探しているものと同じであるかどうかを確認します。

線形探索3

最初の項目が一致しませんでした。だから次のものに移動します。

線形探索4

等々...

これは、一致するものが見つかるまで、またはすべての項目がチェックされるまで行われます。

線形探索5

このアルゴリズムでは、アイテムが見つかったときに停止でき、それ以上調べる必要はありません。

では、線形探索操作を行うのにどのくらい時間がかかりますか?最良の場合、あなたは幸運になる可能性があり、あなたが見ているアイテムはおそらく配列の最初の位置にあります!ただし、最悪の場合、最後の場所でアイテムを見つける前、またはアイテムが配列にないことに気付く前に、すべてのアイテムを確認する必要があります。

したがって、線形探索の複雑さはO(n)です。

検索する要素が最初のメモリブロックを主宰する場合、複雑さはO(1)になります。

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の例

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での例

def linear_search(target, array) counter = 0 while counter < array.length if array[counter] == target return counter else counter += 1 end end return nil end 

C ++での例

int linear_search(int arr[],int n,int num) { for(int i=0;i

Example in Python

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

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 } 

Example in Java

int linearSearch(int[] arr, int element) { for(int i=0;i

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 array return -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.

Target = 5

Array = [ 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.

def global_linear_search(target, array) counter = 0 results = [] while counter < array.length if array[counter] == target results << counter counter += 1 else counter += 1 end end if results.empty? return nil else return results end 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.

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:

  1. Open the middle page of the phonebook
  2. If it has the name we are looking for, we are done!
  3. Otherwise, throw away the half of the phonebook that does not contain the name
  4. Repeat until you find the name or there are no more pages left in the phonebook

[

Original text


Binary vs Linear Search

]

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 ).

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

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:

1 = N / 2^x 

Multiply by 2x:

2^x = N 

Now do the 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.

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.

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.

Binary Search 1

Mark low, high and mid positions in the array.

Binary Search 2

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

Binary Search 3

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

Binary Search 4

Again compare with the middle element.

Binary Search 5

Now, move to the left half.

Binary Search 6

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.

The code for recursive binary search is shown below:

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:

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])  } return search(0, array_length(a) - 1); } 

Ruby implementation

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

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 implementation

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

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; else end = mid - 1; } return -1; } 

Example in Swift

func binarySearch(for number: Int, in numbers: [Int]) -> Int? { var lowerBound = 0 var upperBound = numbers.count while lowerBound < upperBound { let index = lowerBound + (upperBound - lowerBound) / 2 if 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 } 

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; else end = 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 ); else return binarySearch( arr, start, mid - 1 , element); } return -1; }