Мы можем решить эту проблему, используя как линейный, так и бинарный поиск.
Но линейный поиск будет O (n). Двоичный поиск даст O (Logn).
Следовательно, лучше использовать бинарный поиск.
Полная программа:
public class Test4 {
public static void main(String[] args) {
int a[] = {1, 2, 2, 3, 3, 3, 6,6,6,6,6,66,7};
int x = 6;
System.out.println(fix(a,x));
}
private static int fix(int[] a, int x) {
int res = 0 ;
for (int i = 0; i < a.length; i++) {
int ch = a[i];
if(x == ch) {res++ ;}
}
return res;
}
}
Есть еще один вопрос, который задают: 1-й и последний вхождения заданного числа в отсортированный массив.
class Occurence1 {
public static void findFirstAndLast(int a[], int x) {
int first = -1, last = -1;
for (int i = 0; i < a.length; i++) {
if (x == a[i]) {
if (first == -1) {
first = i;
}
// update last
last = i;
} // if
} // for
if (first != -1) {
System.out.println("First Occurrence = " + first);
System.out.println("Last Occurrence = " + last);
}
}// end1
public static void main(String[] args) {
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 8;
findFirstAndLast(arr, x);
}
}
В Python:
def findFirstAndLast(a, x):
first = -1 ; last = -1
for i in range(len(a)) :
if(x == a[i]):
if(first == -1):first = i
# update last if the first contains oter value than -1
last = i
if(first != -1):
print("first => ",first)
print("last =>", last)
a = [1, 2, 3,4, 5, 6, 7, 8, 1, 10, 10]
x = 10
findFirstAndLast(a, x)