Tìm chỉ mục của phần tử giữa (phần tử tối thiểu) Áp dụng Tìm kiếm nhị phân trên mảng con dựa trên các điều kiện sau -
-
Nếu số nằm giữa phần tử bắt đầu và phần tử ở vị trí giữa 1.
-
Sau đó, tìm số trong mảng bắt đầu đến giữa 1 bằng cách sử dụng tìm kiếm nhị phân
-
Nếu số nằm giữa phần tử giữa và phần tử cuối cùng, thì hãy tìm số trong mảng từ giữa đến phần tử cuối cùng bằng cách sử dụng tìm kiếm nhị phân.
Ví dụ
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class Arrays{
public int FindNumberRotated(int[] array, int start, int end, int value){
if (start > end){
return -1;
}
int mid = (start + end) / 2;
if (array[mid] == value){
return mid;
}
if (array[start] <= array[mid]){
if (value >= array[start] && value <= array[mid]){
return FindNumberRotated(array, start, mid - 1, value);
}
return FindNumberRotated(array, mid + 1, end, value);
}
if (value >= array[mid] && value <= array[end]){
return FindNumberRotated(array, mid + 1, end, value);
}
return FindNumberRotated(array, start, mid - 1, value);
}
}
class Program{
static void Main(string[] args){
Arrays a = new Arrays();
int[] arr = { 3, 4, 5, 6, 7, 8, 9, 10, 1, 2 };
int res = a.FindNumberRotated(arr, 0, arr.Length - 1, 1);
Console.WriteLine(res);
}
}
} Đầu ra
8